Typical DP Contest：H - ナップザック

問題

https://atcoder.jp/contests/tdpc/tasks/tdpc_knapsack

よくあるナップザック問題の制約に色の数 C がついた問題である。

考え方

愚直に色の数を集合として持つと O(NW2^C) となる。工夫が必要である。

色ごとに順番にナップザックしていくことを考える。DPとしては以下を定義する。

  • dp[i][j] :=\ i 個以下の色を使って、重さが j 以下の最大の価値
  • ndp[i][j] := 色 c_i を使うことを含めて i 個以下の色を使って、重さが j 以下の最大の価値

とする。このとき i-1 色の結果に色 c_i を使ったDPの更新と、色 c_i のみを使ったDPの更新がある。それぞれで ndp[i][j] を更新した後、 dp[i][j] の結果にマージしていくことを繰り返すと解くことができる。

Submission #3923412 - Typical DP Contest

どこに着目して考察するべきだったか

色ごとにナップザックをして、直前の結果とマージして更新していくDPを考える必要がある。このタイプのDPも経験が必要そう。

何がバグっていたか

得た知見

マージしながら更新する

類題

参考