Typical DP Contest H:ナップザック

問題文

http://tdpc.contest.atcoder.jp/tasks/tdpc_knapsack

解法

物を色ごとにグループ分けした.

dp[i][j]:i種類以下の色を使って,j以下の重さまで許容するときの価値の最大値.

としてdpした.

適当にやったらうまくdp出来ない状況に陥ったので,さらに適当にやりまくったらなんかちゃんと書けた.

コード

#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int>P;


vector<P>V[50];
int N,W,C;

int dp[51][10001];
int main(){
    scanf("%d%d%d",&N,&W,&C);
    for(int i=0;i<N;i++){
        int w,v,c;
        scanf("%d%d%d",&w,&v,&c);c--;
        V[c].push_back(P(w,v));
    }
    for(int i=0;i<50;i++){
        for(int j=C;j>0;j--){
            int dp2[10001]={0};
            for(int k=0;k<V[i].size();k++){
                int w=V[i][k].first,v=V[i][k].second;
                for(int l=W;l>=0;l--){
                    int val=max(dp2[l],dp[j-1][l]);
                    if(l-w>=0)val=max(val,max(dp[j-1][l-w]+v,dp2[l-w]+v));
                    dp2[l]=max(dp2[l],val);
                }
            }
            for(int k=0;k<=W;k++)dp[j][k]=max(dp[j][k],dp2[k]);
        }
    }

    cout<<dp[C][W]<<endl;
    return 0;
}