题解【POJ1014】 Dividing

题目意思

有六种不同的石子,权值为\(1\)~\(6\),给出六种石子的数量,求能否将石子分成权值相等的两份.

解析

这题可以直接用多重背包写,

因为仔细想想,

能够平均分成两份,

也就是能将一部分石子拼成总权值的二分之一.

那么,直接用可行性DP写就行了.

(对于可行性DP请自行上百度吧qwq(因为这又是另一个故事了)

上代码吧:

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

inline int read(){

	int sum=0,f=1;char ch=getchar();

	while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0' && ch<='9'){sum=sum*10+ch-'0';ch=getchar();}

	return f*sum;

}

int a[7],tot=0;

int f[150001],u[150001];

int main(){

	while(1){

		int sum=0;

		for(int i=1;i<=6;i++) a[i]=read(),sum+=a[i]*i;

		if(!sum) break;

		printf("Collection #%d:\n",++tot);

		if(sum%2) {puts("Can't be divided.");puts("");continue;}

		memset(f,0,sizeof(f));f[0]=1;

		for(int i=1;i<=6;i++){

			for(int j=0;j<=sum;j++) u[j]=0;

			for(int j=i;j<=sum;j++){

				if(!f[j]&&f[j-i]&&u[j-i]<a[i]){

					f[j]=1;u[j]=u[j-i]+1;

				}

			}

		}

		if(f[sum>>1]) puts("Can be divided.");

		else puts("Can't be divided.");

		puts("");

	}

	return 0;

}

巴特西

题解【POJ1014】 Dividing

题目意思

解析

最新文章

热门文章

巴特西

题解 【POJ1014】 Dividing

题目意思

解析

最新文章

热门文章

题解【POJ1014】 Dividing