https://atcoder.jp/contests/kupc2019/submissions/13604182
- 初期値は dp[0]=0
- 繰り返しは rep(i, 1, Size(newItem)) rep(j, 0, n * Pow10(4) + 1)
- 更新は if (0 <= j - newItem[i].first) dp[i][j] = max({ dp[i][j], dp[i - 1][j], dp[i - 1][j - newItem[i].first] + newItem[i].second }); など
- 出力は rep(j, 0, W + 1) ans = max(ans, dp.back()[j]);
ナップサックDPの定石としてDPの行を商品、DPの列を程度の要素にする、と暗記する。芋づる式のデータ構造にunion-findを使うのも定石なので暗記する。各要素を集合にしていくと商品インデックスに空白が出来るが、値が0ならDP更新されないので気にせずナップサックの処理を書いて良い。ただし、値0では前のDPを引き継ぐことを忘れずに書く。商品インデックスの先頭にダミーを入れておくと更にDPが書きやすくなる。また、列のDPサイズが
になることに注意する。
