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

Re:这题`DP 应该怎么写啊,我写的DP怎么超时了

Posted by sphinxdwood at 2007-07-30 22:41:34 on Problem 1014
In Reply To:这题`DP 应该怎么写啊,我写的DP怎么超时了 Posted by:wincat at 2007-07-30 17:23:48
我也是啊。超时
#include<iostream>
void print(int id,int isOK){
	if(isOK==1)
		printf("Collection #%d:\nCan be divided.\n\n",id);
	else printf("Collection #%d:\nCan't be divided.\n\n",id);
}
int main(){
	int sum,i,j,k,a[7],time,temp;
	char f[7][10001];
	
	sum=0;
	memset(a,0,sizeof(a));
	for(i=1;i<=6;i++){
		scanf("%d",&a[i]);
		sum+=i*a[i];
	}
	time=1;
	while(sum>0){
		if(sum&1) print(time,0);
		else {
			sum=sum/2;
			memset(f,0,sizeof(f));
			for(i=0;i<=6;i++) f[i][0]=1;
			for(i=1;i<=6;i++)
				for(j=1;j<=sum;j++)
					if(f[i-1][j]==1) f[i][j]=1;
					else for(k=1;k<=a[i];k++)
						if(f[i-1][j-k*i]==1&&j-i*k>=0)
							f[i][j]=1;
			temp=0;
			for(i=1;i<=6;i++)
				if(f[i][sum]==1){
					temp=1;
					break;
				}
			print(time,temp);
		}
		sum=0;
		memset(a,0,sizeof(a));
		for(i=1;i<=6;i++){
			scanf("%d",&a[i]);
			sum+=i*a[i];
		}
		time++;
		
	}
	return 0;
}


			

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