POJ 1950 Dessert
发布时间：2020-12-13 20:40:55 所属栏目：PHP教程 来源：网络整理
导读：题目链接~~ 题意 ： 给你 n ( 1 = n = 15) 个数（1 . 2 . 3 . 4 ....） 在这些数中间添加 ，- ,。，使得终究的计算结果为 0 ，如果情况不大于 20 种 ，则输出全部，否则最多输出 前20 种，按字典序输出。 解题思路 ： 这题和在广东区域赛的热身赛的1题差不多
|
题目链接~~ 题意 ： 给你 n ( 1 <= n <= 15) 个数（1 . 2 . 3 . 4 ....） 在这些数中间添加 + ，- ,。，使得终究的计算结果为 0 ，如果情况不大于 20 种 ，则输出全部，否则最多输出 前20 种，按字典序输出。 解题思路 ：这题和在广东区域赛的热身赛的1题差不多，深搜枚举所有情况，就是处理点的时候需要注意，同时处理的的情况大于等于 10 的数字应当乘 100 。 代码： #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <stack>
#include <queue>
#include <map>
#include <string>
#include <vector>
#include <cmath>
using namespace std ;
const int MX = 100 + 5 ;
const int INF = 0x3f3f3f3f ;
int n,ans ;
char s[MX] ;
void dfs(int num,int sum,int temp,int pre,int di) // sum 已计算的总和
{
if(n == num)
{
if(s[num⑴] != '.')
sum += temp*pre ;
else // 大于等于 10 的时候特殊
{
if(num < 10)
sum += (temp*10 + num)*pre ;
else sum += (temp*100 + num)*pre ;
}
if(sum) return ;
ans++ ;
if(ans > 20) return ;
cout<<1 ;
for(int i = 2 ;i <= n ; ++i)
cout<<" "<<s[i⑴]<<" "<<i ;
cout<<endl ;
return ;
}
int Temp = temp ;
if(s[num⑴] == '.')
{
if(num < 10)
Temp = temp*10 + num ;
else Temp = temp*100 + num ;
}
s[num] = '+' ; // +
dfs(num+1,sum + Temp*pre,num+1,1,0) ;
s[num] = '-' ; // -
dfs(num+1,⑴,0) ;
s[num] = '.' ; // .
if(!di) // 第1次放点
dfs(num+1,sum,num,pre,di+1) ;
else
{
if(num < 10) // 注意 >= 10 是需要乘 100
dfs(num+1,temp*10 + num,di+1) ;
else dfs(num+1,temp*100 + num,di+1) ;
}
}
int main()
{
while(~scanf("%d",&n))
{
ans = 0 ;
s[0] = '+' ; //
dfs(1,0) ; //主要是点的情况特殊
cout<<ans<<endl ;
}
return 0 ;
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |