记录编号	542117	评测结果	A
题目名称	[POJ 1014] 大理石分割	最终得分	100
用户昵称	瑆の時間~無盡輪迴·林蔭	是否通过	通过
代码语言	C++	运行时间	0.123 s
提交时间	2019-09-20 11:33:31	内存使用	15.95 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
bool dp1[10][120001],dp2[10][120001];
int a[10];
int mid,tot;
int main()
{
	freopen("dividestone.in","r",stdin);
	freopen("dividestone.out","w",stdout);
	while(1) 
	{
		mid=0;
		tot++;
		for(int i=1;i<=6;i++)
		{
			scanf("%d",&a[i]);
		}
		for(int i=1;i<=6;i++)
		{
			mid+=a[i]*i;
		}
		if(mid==0)
			return 0;
		if(mid%2==1)
		{
			cout<<"Collection #"<<tot<<":"<<endl;
			cout<<"Can't be divided."<<endl;
			continue;
		} 
		memset(dp1,false,sizeof(dp1));
		memset(dp2,false,sizeof(dp2));
		for(int i=1;i<=7;i++)
		{
			dp1[i][0]=1;
			dp2[i][0]=1;
		}
		mid=mid/2;
		for(int i=0;i<3;i++)
		{
			for(int j=0;j<=mid;j++)
			{
				if(!dp1[i][j])
					continue;
				for(int k=0;k<=a[i+1];k++)
				{
					dp1[i+1][j+k*(i+1)]=1;
					if(j+k*i+k>mid)
						break;
				}
			}
		}
		for(int i=3;i<6;i++)
		{
			for(int j=0;j<=mid;j++)
			{
				if(!dp2[i][j])
					continue;
				for(int k=0;k<=a[i+1];k++)
				{
					dp2[i+1][j+k*(i+1)]=1;
					if(j+k*(i+1)>mid)
						break;
				}
			}
		}
		for(int i=0;i<=mid;i++)
		{
			if(dp1[3][i]==1&&dp2[6][mid-i]==1)
			{
				cout<<"Collection #"<<tot<<":"<<endl;
				cout<<"Can be divided."<<endl;
				break;
			}
			if(i==mid)
			{
				cout<<"Collection #"<<tot<<":"<<endl;
				cout<<"Can't be divided."<<endl;
			}
		}
	}
	return 0;
}