Typical DP Contest H - ナップザック

問題

tdpc.contest.atcoder.jp

解法

sugim さんの解法を参考にしました。O(NCW) から計算量を落とせなくてずっと悩んでたんですが多分 O(NCW)…？(間違ってたらすみません)ちなみに僕が考えていた解法より 2 倍くらい定数倍早くて実装も楽でした。

各色ごとに dp を更新していくことを考えます。

各色ごとに, たとえその後その色を使って品物を増やすことがなくても, 「色を一色増やした」という前提で考えても問題ありません(もし一色も増やしてなかったら損なので, 結局色を使っていない側が得になるため)。

色を一色増やしたとした場合, その後はいつものナップザック問題のように dp を更新していけば良いです。

const int MAXN = 111;
int w[MAXN], v[MAXN], c[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, W, C;
    cin >> N >> W >> C;
    for (int i = 0; i < N; i++) {
        cin >> w[i] >> v[i] >> c[i];
    }
    vector<vi> dp(C+1, vi(W+1));
    for (int i = 1; i <= 50; i++) {
        vector<vi> _dp(C+1, vi(W+1));
        // 色を一色増やすとする
        for (int x = 0; x+1 <= C; x++) {
            _dp[x+1] = dp[x];
        }
        for (int j = 0; j < N; j++) if (c[j] == i) {
            for (int x = 1; x <= C; x++) {
                for (int y = W-w[j]; y >= 0; y--) {
                    _dp[x][y+w[j]] = max(_dp[x][y+w[j]], _dp[x][y]+v[j]);
                }
            }
        }
        for (int x = 0; x <= C; x++) for (int y = 0; y <= W; y++) {
            dp[x][y] = max(dp[x][y], _dp[x][y]);
        }
    }
    cout << dp[C][W] << endl;
    return 0;
}