SRM 651 div2 Med

問題概要

N個の数列がある。これを、N/2個に分割し、かつ、それらの数列の和を等しくすることは可能か。可能ならば、"Possible"、不可能ならば、"Impossible"と出力せよ。

制約

• 1 ≤ N ≤ 50
• 1 ≤ value ≤ 50

解法

dpする。
dp[個数][和] := 作ることが可能かどうか。
最終的にdp[個数/2][和/2]がtrueならば"Possible"、falseならば"Impossible"となる。

コード

#define MAX 2510

class FoxAndSouvenirTheNext {
public:
  string ableToSplit(vector <int> value) {
    int N = value.size();
    bool dp[51][MAX];
    memset(dp,false,sizeof(dp));
    int sum = accumulate(value.begin(),value.end(),0);
    if(N & 1 || sum & 1){ return "Impossible"; }
    dp[0][0] = true;
    for(int i = 0 ; i < N ; i++){
      for(int j = i ; j >= 0 ; j--){
	for(int k = 2500 ; k >= 0 ; k--){
	  if(dp[j][k]){
	    dp[j+1][k+value[i]] = true;
	  }
	}
      }
    }
    return (dp[N/2][sum/2] ? "Possible" : "Impossible");
  }
};