Typical DP Contest H - ナップザック

問題

n個の品物があり、i番目の品物は重さがwi, 色がci, 価値がviである。
ナップサックに重さの合計がW以下, 色の合計がC色以下であるように品物を詰める。


価値の最大はいくつか。

制約条件

n≦100
W≦10000
C≦50

方針

品物を色ごとにまとめる。
色ごとに、
dp[1回以上何かの品物を使ったか][今までの色の合計][重さの合計]
を更新する(普通のナップサック問題的な)DPをして、


一つの色が終わったら、そのつど
dp[0][i][j]にdp[0][i][j]とdp[1][i][j]をまとめる。

ソースコード

int n, W, C, dp[2][51][100010];
map<int, vector<pi> > m;
 
int main(){
	cin >> n >> W >> C;
	rep(i, n){
		int w, c, v;
		cin >> w >> v >> c;
		m[c].pb(mp(w, v));
	}
	
	int i = 0, ans = 0;
	each(it, m){
		memset(dp[1], -1, sizeof(dp[1]));
		each(j, it->second) for(int l = W; l >= 0; l--) for(int k = C; k >= 0; k--) rep(u, 2){
			
			if(l + j->first > W || k + !u > C || dp[u][k][l] < 0) continue;
			dp[1][k + !u][l + j->first] = max(dp[1][k + !u][l + j->first], dp[u][k][l] + j->second);
			ans = max(ans, dp[1][k + !u][l + j->first]);
			
		}
		rep(j, C+1) rep(k, W+1) dp[0][j][k] = max(dp[0][j][k], dp[1][j][k]);
	}
	cout << ans << endl;
	
	return 0;
}