POJ 1416 Shredding Company(二)
esponding output takes one of the following three types :
sum part1 part2 ...
rejected
error
In the first type, partj and sum have the following meaning :
1.Each partj is a number on one piece of shredded paper. The order of partj corresponds to the order of the original digits on the sheet of paper.
2.sum is the sum of the numbers after being shredded, i.e., sum = part1 + part2 +...
Each number should be separated by one space.
The message error is printed if it is not possible to make any combination, and rejected if there is
more than one possible combination.
No extra characters including spaces are allowed at the beginning of each line, nor at the end of each line.
Sample Input
50 12346
376 144139
927438 927438
18 3312
9 3142
25 1299
111 33333
103 862150
6 1104
0 0
Sample Output
43 1 2 34 6
283 144 139
927438 927438
18 3 3 12
error
21 1 2 9 9
rejected
103 86 2 15 0
rejected
Source
Japan 2002 Kanazawa
用dfs搜就可以了，只是我一开始做题的时候用的全局变量，结果测试数据都无法过掉，于是不断的检查无法查出错误在什么地方，实在没办法了，就设置了变量，查看每一层的递归函数中值的变化，最后终于查出错误原因了。然后改的局部变量。 总之一句话 全局变量要慎用啊
[cpp]
#include
#include
#include
int n;
char s1[10];
int l,key,b[30],res[30],top2,col,k;
int max,m;
int main()
{
void dfs(int x,int top1);
int i,j,s,t;
while(scanf("%d %s",&n,s1)!=EOF)
{
l=strlen(s1);
for(i=0,s=0;i<=l-1;i++)
{
s=s*10+s1[i]-'0';
}
if(!n&&!s)
{
break;
}
if(s==n)
{
printf("%d %d\n",n,n);
continue;
}
top2=0;
max=-1;
key=0; k=0;
dfs(0,0);
if(k==1)
{
printf("rejected\n");
}else if(key==0)
{
printf("error\n");
}else
{
printf("%d",max);
for(i=0;i<=top2;i++)
{
printf(" %d",res[i]);
}
printf("\n");
}
}
return 0;
}
void dfs(int x,int top1)
{
int i,j,u,v,s,check;
for(j=1;j<=l;j++)
{
for(u=0,s=0,check=0;u<=j-1;u++)
{
if((x+u)>=l)
{
check=1;
}
s=s*10+s1[x+u]-'0';
}
if(!check)
{
b[top1]=s;
if((x+u)==l)
{
for(i=0,s=0;i<=top1;i++)
{
s+=b[i];
}
if(s<=n)
{
if(s>max)
{
k=0;
key=1;
max=s;
top2=top1;
for(i=0;i<=top1;i++)
{
res[i]=b[i];
}
}else if(s==max)
{
key=-1; k=1;
return ;
}
}
}else
{
dfs(x+j,top1+1);
}
}else
{
break;
}
}
}