POJ 1416

  1 #include <stdio.h>
  2 #include <iostream>
  3 #include <algorithm>
  4     
  5 using namespace std;
  6 
  7 int LEN;
  8 int target;
  9 int sum;
 10 int ans;
 11 int f_ans[10];
 12 int _max;
 13 int last_index;
 14 int index;
 15 int num_array[10];
 16 int print[10];
 17 void GET_LEN(int num);
 18 void DFS(int time,int state);
 19 int main()
 20 {
 21     //freopen("acm.acm","r",stdin);
 22     //freopen("out.acm","w",stdout);
 23     int num;
 24     int i;
 25 
 26     while(cin>>target>>num && (target || num))
 27     {
 28         ans = 0;
 29         _max = -1;
 30         index = 0;
 31         sum = 0;
 32         GET_LEN(num);
 33         reverse(num_array,num_array+LEN);
 34         DFS(0,0);
 35         if(ans == 0)
 36         {
 37             cout<<"error"<<endl;
 38         }
 39         else if(ans > 1)
 40         {
 41             cout<<"rejected"<<endl;
 42         }
 43         else
 44         {
 45             cout<<_max<<" ";
 46             for(i = 0; i < last_index; ++ i)
 47             {
 48                 cout<<f_ans[i]<<" ";
 49             }
 50             cout<<endl;
 51         }
 52         /*for(i = 0; i < LEN; ++ i)
 53         {
 54             cout<<num_array[i]<<" ";
 55         }
 56         */
 57         //cout<<endl;
 58         //cout<<LEN<<endl;
 59         
 60     }
 61     return 0;
 62 }
 63 
 64 void DFS(int time,int state)
 65 {
 66     if(time == LEN)
 67     {
 68         if(sum > target)
 69         {
 70             return;
 71         }
 72         else
 73         {
 74             if(sum == _max)
 75             {
 76                 ++ ans;
 77             }
 78             else if(sum > _max)
 79             {
 80                 int i;
 81                 _max = sum;
 82                 for(i = 0; i < index; ++ i)
 83                 {
 84                     f_ans[i] = print[i];
 85                 }
 86                 last_index = index;
 87                 ans = 1;
 88             }
 89         }
 90     }
 91     else
 92     {
 93         print[index ++] = state*10 + num_array[time];
 94         sum += print[index-1];
 95         DFS(time + 1,0);
 96         sum -= print[index-1];
 97         -- index;
 98         if(time + 1 < LEN)
 99         {
100             DFS(time + 1,state*10+num_array[time]);
101         }
102     }
103 }
104 
105 void GET_LEN(int num)
106 {
107     LEN = 0;
108     while(num)
109     {
110         num_array[LEN ++] = num%10;
111         num /= 10;
112     }
113 }
关注我的公众号，当然，如果你对Java, Scala, Python等技术经验，以及编程日记，感兴趣的话。
技术网站地址： vmfor.com