USACO 2.3.3 Zero Sum 深搜

Zero Sum Consider the sequence of digits from 1 through N (where N=9) in increasing order: 1 2 3 ... N. Now insert either a `+' for addition or a `-' for subtraction or a ` ' [blank] to run the digits together between each pair of digits (not in front of the first digit). Calculate the result that of the expression and see if you get zero. Write a program that will find all sequences of length N that produce a zero sum. PROGRAM NAME: zerosum INPUT FORMAT A single line with the integer N (3 <= N <= 9). SAMPLE INPUT (file zerosum.in) 7 OUTPUT FORMAT In ASCII order, show each sequence that can create 0 sum with a `+', `-', or ` ' between each pair of numbers. SAMPLE OUTPUT (file zerosum.out) 1+2-3+4-5-6+7 1+2-3-4+5+6-7 1-2 3+4+5+6+7 1-2 3-4 5+6 7 1-2+3+4-5+6-7 1-2-3-4-5+6+7 /*---------------------------------------------------------------*/ 再一次說明了USACO會幫著你復習，這一道題終於不是動態歸劃了，而是簡單的深搜。單純地遍歷所有情況即可，由於最多9個數，8個符號，最多3的8次方種。 程序： [cpp]   /*  ID:zhaorui3  PROG:zerosum  LANG:C++  */   # include <iostream>   # include <fstream>   using namespace std;      int operations[9] = {0};            //0:nothing , 1:+, 2:-   int templeft = 0 , tempRight = 0;      int main()   {          operations[0] = 1;       ifstream fin("zerosum.in");       ofstream fout("zerosum.out");       int end;       fin >> end;       while(true)     //這層循環是用來遍歷所有符號的       {           templeft = 0;           tempRight = 0;           for(int j = 1 ; j <= end ; j++ )                 //這層循環是用來計算當前符號下的結果的           {               if(operations[j-1] == 1)            //   +               {                   int k = j;                   tempRight = j;                      while(k <= end-1 && operations[k] == 0)                   {                       tempRight = tempRight*10 + k+1;                       k++;                       j++;                   }                   templeft = templeft + tempRight;                   tempRight = 0;                   continue;               }                  if(operations[j-1] == 2)        // -               {                   int k = j;                   tempRight = j;                      while(k <= end-1 && operations[k] == 0)                   {                       tempRight = tempRight*10 + k+1;                       k++;                       j++;                   }                   templeft = templeft - tempRight;                   tempRight = 0;                   continue;               }           }              if(templeft == 0)           {               fout << 1;               for(int m = 0 ; m <= end-2 ; m++ )               {                   switch(operations[m+1])                   {                   case 1:                       fout << '+';                       break;                   case 2:                       fout << '-';                       break;                   case 0:                       fout << ' ';                       break;                   }                   fout << m+2;               }               fout << endl;           }           operations[end-1]++;           for(int m = end-1 ; m > 1 ; m-- )           {               if(operations[m] > 2)               {                   operations[m] = 0;                   operations[m-1]++;               }           }              if(operations[1] > 2)               break;       }   }