題目鏈接：http://acm.pku.edu.cn/JudgeOnline/problem?id=1416
所用算法：枚舉（01枚舉）
注意事項(xiàng)：注意位操作，要細(xì)心
提交情況：半個(gè)月前（12月4號(hào)，兩次wa），今天重新讀題又完全換思路重寫了一遍，ac
心得體會(huì)：數(shù)據(jù)量小，直接枚舉就可以，并不一定必須要深搜或剪枝。這道題如果深搜的話，剪枝的條件也是非常明顯的。代碼很亂，希望半個(gè)月后review的話還能看得懂。
1 #include<iostream>
2 #include<stdio.h>
3 #include<math.h>
4 #include<stdlib.h>
5 #include<string.h>
6 using namespace std;
7
8 int calvalue(int t,int sum)
9 {
10 int result=0;
11 int j=0;
12 for(int i=0;i<=5;i++)
13 {
14 if(t&(1<<i))
15 {
16 result=result+sum%(int)pow(10,j+1);
17 sum=sum/(int)pow(10,j+1);
18 //printf("%d %d\\n",result,sum);
19 j=0;
20 }
21 else
22 {
23 j++;
24 }
25 }
26 return result+sum;
27 }
28
29 int printvalue(int t,int sum)
30 {
31 int stack[10];
32 int top=0;
33 int j=0;
34 for(int i=0;i<=5;i++)
35 {
36 if(t&(1<<i))
37 {
38 stack[top++]=sum%(int)pow(10,j+1);
39 sum=sum/(int)pow(10,j+1);
40 j=0;
41 }
42 else
43 {
44 j++;
45 }
46 }
47 stack[top++]=sum;
48 while(top!=1)
49 {
50 printf("%d ",stack[--top]);
51
52 }
53 printf("%d\\n",stack[0]);
54 }
55
56 int main()
57 {
58 int target;
59 char num[7];
60 //freopen("data.in","r",stdin);
61 while(scanf("%d%s",&target,num)==2)
62 {
63 if(target==0&&num[0]=='0')
64 break;
65 int sum=0;
66 int flag=0;
67 int length=strlen(num);
68 int minvalue=0;
69 int partition=-1;
70 for(int i=0;i<length;i++)
71 {
72 sum=10*sum+num[i]-'0';
73 minvalue+=num[i]-'0';
74 }
75
76 if(sum==target)
77 {
78 printf("%d %d\\n",target,sum);
79 continue;
80 }
81 else if(minvalue>target)
82 {
83 printf("error\\n");
84 continue;
85 }
86 else
87 {
88 minvalue=0;
89 int mysum=0;
90 int times=1<<(length-1);
91 for(int j=0;j<times;j++)
92 {
93 mysum=calvalue(j,sum);
94 if(mysum==minvalue)
95 {
96 flag=1;
97 }
98 else if(mysum<=target&&mysum>minvalue)
99 {
100 minvalue=mysum;
101 flag=0;
102 partition=j;
103 }
104 }
105 }
106 if(flag==1)
107 {
108 printf("rejected\\n");
109 }
110 else
111 {
112 printf("%d ",minvalue);
113 printvalue(partition,sum);
114 }
115
116 }
117 }
118