Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

第一次自己写回溯,居然一A,连自己都吓到了。。太高兴了。。贴代码显摆下哈哈~~

Posted by NARUTOACM at 2009-09-04 10:06:17 on Problem 1416
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator