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

终于AC了,囧rz................

Posted by kuki at 2010-08-09 18:00:37 on Problem 1014
#include<stdio.h>
#define wds -9999999
int f[120005];
int V;

int max(int x,int y){return x>y?x:y;}

void ZeroOnePack(int cost,int weight)
{
	int v;
	for(v=V;v>=cost;v--)
		f[v]=max(f[v],f[v-cost]+weight);
}

void CompletePack(int cost,int weight)
{
	int v;
	for(v=cost;v<=V;v++)
		f[v]=max(f[v],f[v-cost]+weight);

}

void MultiplePack(int cost,int weight,int mount)
{
	if(cost*mount>=V)
	{
		CompletePack(cost,weight);
		return;
	}
	int k=1;
	while(k<mount)
	{
		ZeroOnePack(k*cost,k*weight);
		mount-=k;
		k=k*2;
	}
	ZeroOnePack(mount*cost,mount*weight);
}

int main()
{
//	freopen("in.txt","r",stdin);
	int n[7],i;
	int num=0;
	while(scanf("%d%d%d%d%d%d",&n[1],&n[2],&n[3],&n[4],&n[5],&n[6]))
	{
		V=0;
		for(i=1;i<=6;i++) V+=i*n[i];
		if(V==0) break;
		num++;
		if(V%2!=0)
		{
			printf("Collection #%d:\n",num);
			printf("Can't be divided.\n\n");
			continue;
		}
		V=V/2;
		f[0]=0;
		for(int ii=1;ii<=V;ii++)
			f[ii]=wds;
	//	else
		{
			for(i=1;i<=6;i++)
			{

				MultiplePack(i,i,n[i]);
			}
		//	f[1],f[2],f[3],f[4],f[5],f[6];
			if(V==f[V])
			{
				printf("Collection #%d:\n",num);
				printf("Can be divided.\n\n");
			}
			else
			{
				printf("Collection #%d:\n",num);
				printf("Can't be divided.\n\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