其实是没什么难度的题,但是自己写错了一个字母,一直wa了下午都不知道是怎么回事,晚上才看到,郁闷啊~~~
题目是一个深搜,做不做优化都可以但是本着优秀代码的原则还是应该修枝一下下的,不过不要像我一样,自以为自己在深搜之前比较了target和shred的相等的情况是一个优化,其实在深搜的过程中还是搜索了这种情况时间也没有节省,更郁闷的是自己的优化还出现了一个很要命的bug,最后还是只好把那个自以为得意的部分给扔了…………
源代码:
//target:
//1.是否相等;
//2.比目标数小或等的最大数sum;
//////出现相同返回reject;
//////没有出现返回error;
//////出现返回 sum;
#include <iostream>
char shred[9]={0};
int target;
int CuttedNumber[9]={0};
int n;
int pro[7]={0};
int protemp[7]={0};
int sum;
int reject=-1;
using namespace std;
void CutNumber()
{
n=strlen(shred);
for(int i=0;i<n;i++)
CuttedNumber[i]=(int)shred[i]-48;
return ;
}
void changepro()
{
for(int i=0;i<n;i++)
{
pro[i]=protemp[i];
}
return ;
}
int yforyy(int y,int yy)
{
int temp=0;
int ten_m=1;
for(int i=yy;i>=y;i--)
{
protemp[i]=y;
temp+=CuttedNumber[i]*ten_m;
ten_m*=10;
}
return temp;
}
void search(int y,int yy, int sumtemp)
{
sumtemp+=yforyy(y,yy);
if(yy+1==n)
{
if(sum==sumtemp)
{
reject=sumtemp;
}
else if(sum<sumtemp&&sumtemp<=target)
{
sum=sumtemp;
changepro();
}
}
else
{
if(sumtemp<=target)
{
for(int i=0;yy+1+i<n;i++)
search(yy+1,yy+1+i,sumtemp);
}
else
return ;
}
}
main()
{
while(cin>>target>>shred&&(target!=0||shred[0]!='0'))
{
sum=-2;
CutNumber();
for(int i=0;i<n;i++)
search(0,i,0);
if(reject==sum)
cout<<"rejected"<<endl;
else if(sum==-2)
cout<<"error"<<endl;
else
{
cout<<sum<<" ";
for(int i=0;i<n;i++)
{
cout<<shred[i];
if(pro[i]!=pro[i+1]&&i+1<n)
cout<<" ";
}
cout<<'\n';
}
reject=-1;
memset(shred,0,sizeof(shred));
memset(pro,0,sizeof(pro));
memset(protemp,0,sizeof(protemp));
memset(CuttedNumber,0,sizeof(CuttedNumber));
}
return 0;
}