1014:Dividing

問題文
http://poj.org/problem?id=1014

1から6までの価値がついたビー玉を二人で分けたい。
ビー玉の個数が与えられるので同じ価値になるように
わけられるかどうか判定せよ。

動的計画法で解いた。
ビー玉の価値の合計の半分が作れればよい。
個数制限つき部分和問題と同じ。

dp[ビー玉の価値-1][作る価値]:=価値i-1のビー玉の余った個数

#include<iostream>
#include<algorithm>

using namespace std;

int main(void){
	
	int m[7],t=1;
	
	
	while(true){
		if(t!=1)cout << endl;
		int K=0;
		for(int i=0;i<6;i++)cin >> m[i],K+=m[i]*(i+1);
		if(K==0)break;
		
		if(K%2){
			cout << "Collection #" << t << ":" << endl;
			cout << "Can't be divided." << endl;
			t++;
			continue;
		}
		
		K/=2;
		
		int dp[120001];
		fill(dp,dp+120001,-1);
		dp[0]=0;
		
		for(int i=0;i<6;i++){
			for(int j=0;j<=K;j++){
				if(dp[j]>=0)dp[j]=m[i];
				else if(j<i+1 || dp[j-i-1]<=0)dp[j]=-1;
				else dp[j]=dp[j-i-1]-1;
			}
		}
		cout << "Collection #" << t << ":" << endl;
		if(dp[K]>=0)cout << "Can be divided." << endl;
		else cout << "Can't be divided." << endl;
		
		t++;
	}
	return 0;
}