POJ 1950 Dessert

题目链接~~

题意 ： 给你 n ( 1 <= n <= 15) 个数（1 . 2 . 3 . 4 ....） 在这些数中间添加 + ，-  ,。，使得最终的计算结果为 0 ，如果情况不大于 20 种 ，则输出全部，否则最多输出 前20 种，按字典序输出。

解题思路 ：这题和在广东区域赛的热身赛的一题差不多，深搜枚举所有情况，就是处理点的时候需要注意，同时处理的的情况大于等于 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-1] != '.')
       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-1]<<" "<<i ;
      cout<<endl ;
      return ;
       }
      int Temp = temp ;
      if(s[num-1] == '.')
       {
      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 ,-1 ,0) ;
       s[num] = '.' ;  // .
      if(!di) // 第一次放点
       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 ;
      }
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/45421705