TopCoder SRM 651 Div2 Medium FoxAndSouvenirTheNext

SRM651に参加。
Easy落とすわChallenge失敗するわMedium解けないわで散々だったが、unratedに救われた…。

問題

N個のお土産があり、それぞれの価値V[i]が与えられる。
N個のお土産を数を半分かつ価値の総計を半分になるように分けられるか。

解法

V[i]の総和が2500と小さいので、[お土産の数][お土産の総価値]を状態に取って、その状態に到達可能かDPすればよい。

class FoxAndSouvenirTheNext {
	public:
	string ableToSplit(vector <int> V) {
		int N=V.size();
		int tot=0;
		int dp[51][3000]={};
		int i,v,x;
		
		FOR(i,N) tot+=V[i];
		if(N%2 || tot%2) return "Impossible";
		
		dp[0][0]=1;
		FOR(i,N) {
			for(x=i;x>=0;x--) {
				for(v=2500;v>=0;v--) if(dp[x][v]) dp[x+1][v+V[i]]=1;
			}
		}
		
		if(dp[N/2][tot/2]) return "Possible";
		return "Impossible";
	}
}

まとめ

余りに典型なDPだけど、なんで今更こんなの出したのだろう。