程序员人生 网站导航

POJ 1950 Dessert

栏目:php教程时间:2015-05-22 08:11:11

题目链接~~

题意 : 给你 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 ; }




------分隔线----------------------------
------分隔线----------------------------

最新技术推荐