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