| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
第一次自己写回溯,居然一A,连自己都吓到了。。太高兴了。。贴代码显摆下哈哈~~#include<iostream>
using namespace std;
int a[100][100];
int m[100];
int ans[100];
int p[1000000];
int sum,mm,an;
int MAX;
int t,len;
void Backtrack(int i,int l);
int main()
{
int i,j;
char num[100];
while(cin>>t>>num)
{
memset(a,-1,sizeof(a));
len=strlen(num);
if(t==0&&len==1&&num[0]=='0')
break;
for(i=0;i<len;i++)
{
a[i][i]=num[i]-48;
for(j=i+1;j<len;j++)
a[i][j]=a[i][j-1]*10+num[j]-48;
}
Backtrack(0,len);
if(MAX==0)
cout<<"error"<<endl;
else if(p[MAX]>=1)
cout<<"rejected"<<endl;
else
{
cout<<MAX;
for(i=0;i<an;i++)
cout<<' '<<ans[i];
cout<<endl;
}
p[MAX]=0;
mm=0;
sum=0;
MAX=0;
}
return 0;
}
void Backtrack(int i,int l)
{
int j;
if(l==0)
{
if(sum==MAX)
p[MAX]++;
if(sum>MAX)
{
p[MAX]=0;
an=mm;
memcpy(ans,m,sizeof(int)*mm);
MAX=sum;
}
return;
}
for(j=i;j<l+i;j++)
{
if(sum+a[i][j]<=t)
{
m[mm++]=a[i][j];
sum+=a[i][j];
Backtrack(1+j,l-1-(j-i));
sum-=a[i][j];
mm--;
}
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator