Typical DP Contest H : ナップザック

問題リンク :
H: ナップザック - Typical DP Contest | AtCoder

問題概要 : 日本語なので略

解法 :
まずナップザックに入れるものを色の番号が小さい順にソートする
（同じ色のものは連続した場所に存在するようにしたいだけ）
通常のナップザックに加えて、今追加しようとしている色が既に追加されているかされていないかという情報を持たせる
下記の配列にあるstate(0か1)がその情報を表す
dp[i][state][c][w] := i番目のものを追加しようとしていて、i番目のものと同じ色を既に追加したかどうか(state), 現在の色の数(c), 重みの総和(w) としたときの最大値

コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

struct Data {
  int w,v,c;
  bool operator < ( const Data &dat ) const {
    if( c != dat.c ) return c < dat.c;
    if( w != dat.w ) return w < dat.w;
    return v < dat.v;
  }
};

int N,W,C,dp[2][2][60][10010];
Data data[101];

void compute() {
  memset(dp,-1,sizeof(dp));
  dp[0][0][0][0] = 0;
  sort(data,data+N);
  int maxi = 0;
  rep(i,N) { 
    int cur = i & 1;
    int next = !cur;
    rep(j,2) rep(k,C+1) rep(l,W+1) dp[next][j][k][l] = -1;
    Data &info = data[i];
    rep(j,2) {
      rep(k,C+1) {
	rep(l,W+1) {
	  if( dp[cur][j][k][l] == -1 ) continue;
	  dp[next][j][k][l] = max(dp[next][j][k][l],dp[cur][j][k][l]);
	  int color = k + !j;
	  if( color > C || l+info.w > W ) continue;
	  int &v = dp[next][1][color][l+info.w];
	  v = max(v,dp[cur][j][k][l]+info.v);
	  maxi = max(maxi,v);
	}
      }
    }
    if( i+1 < N && info.c != data[i+1].c ) {
      rep(k,C+1) rep(l,W+1) {
	dp[next][0][k][l] = max(dp[next][0][k][l],dp[next][1][k][l]);
	dp[next][1][k][l] = -1;
	maxi = max(maxi,dp[next][0][k][l]);
      }
    }
  }
  cout << maxi << endl;
}

int main() {
  cin >> N >> W >> C;
  rep(i,N) cin >> data[i].w >> data[i].v >> data[i].c;
  compute();
  return 0;
}