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:刚看完背包9讲之第3讲,照着写了写,贴出来献丑!

Posted by DPkiller at 2010-10-14 02:07:16 on Problem 1014
In Reply To:刚看完背包9讲之第3讲,照着写了写,贴出来献丑! Posted by:damacheng009 at 2010-09-27 23:15:26
#include<iostream>
using namespace std;
int a[7],num[60005],dp[60005];
int main()
{
	int i,j,t=1;
	while(scanf("%d%d%d%d%d%d",&a[1],&a[2],&a[3],&a[4],&a[5],&a[6])==6)
	{
		int sum=0,total=0;
		for(i=1;i<=6;i++)sum+=a[i],total+=i*a[i];
		if(!sum)break;
		printf("Collection #%d:\n",t++);
		if(total&1)
		{
			puts("Can't be divided.\n");
			continue;
		}
		total/=2;
		memset(dp,0,sizeof(dp));
		dp[0]=1;
		for(i=1;i<=6;i++)
		{
			memset(num,0,sizeof(num));
			for(j=i;j<=total;j++)
			{
				if(dp[j]||!dp[j-i]||num[j-i]>=a[i])continue;
				dp[j]=1;
				num[j]=num[j-i]+1;
			}
		}
		if(dp[total]) puts("Can be divided.\n");
		else puts("Can't be divided.\n");		
	}	
	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