POJ 1950 Dessert
来源：程序员人生 发布时间：2015-05-22 08:11:11 阅读次数：2435次
题目链接~~
题意 ： 给你 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 ,sum + Temp*pre ,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 ,sum , temp*10 + num ,pre ,di+1) ;
else dfs(num+1 ,sum ,temp*100 + num ,pre ,di+1) ;
}
}
int main()
{
while(~scanf("%d" ,&n))
{
ans = 0 ;
s[0] = '+' ; //
dfs(1 ,0 ,1 ,1 ,0) ; //主要是点的情况特殊
cout<<ans<<endl ;
}
return 0 ;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
