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

多重背包+dp (附代码)

Posted by pengshihui at 2010-07-18 10:48:36 on Problem 1014
#include "stdio.h"
#include "memory.h"

int result [3][10000*6+1];

int main(void)
{
	int i,sum=0,con=0,j,l,flag=0,temp,k,count[2],front,last;
	int a[6];
	while(++con)
	{
		flag=0;
		sum=0;
		for(i=0;i!=6;++i)	
		{
			scanf("%d",a+i);
			if(a[i]!=0) flag=1;
			sum+=a[i]*(i+1);
		}
		if(flag==0) return 0;
		if(sum%2==1) { printf("Collection #%d:\nCan't be divided.\n\n",con);continue;}
		sum/=2;
		memset(result[2],0,sizeof(int)*60001);
		result[2][0]=1;
		result[0][0]=0;
		front=1;last=0;
		count[0]=1;
		count[1]=0;
		for(i=6;i!=0;--i)
		{
			for(j=a[i-1];j>0;--j)
			{
				if(front==1){front=0;last=1;}
				else {front=1;last=0;}
				count[last]=0;
				for(k=count[front]-1;k>=0;--k)
				{
					temp=result[front][k]+i;
					if(temp==sum) {result[2][sum]=1; goto lo;}
					if(temp<sum&&result[2][temp]!=1)
					{
						result[2][temp]=1;
						result[last][count[last]++]=temp;
					}
				}
			}
			count[last]=0;
			for(j=0;j<=sum;++j)
			{
				if(result[2][j])
					result[last][count[last]++]=j;
			}
		}
lo:	if(result[2][sum]==1)
			printf("Collection #%d:\nCan be divided.\n\n",con);
		else printf("Collection #%d:\nCan't be divided.\n\n",con);
	}
	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