AtCoder Regular Contest 027 C: 最高のトッピングにしような

またまた DP 自力で解けた記念。

問題概要

原文 → C: 最高のトッピングにしような - AtCoder Regular Contest 027 | AtCoder

種類のトッピングがある。トッピング は 枚のチケットを交換することで入手でき、その価値は である。

チケットにはスペシャルチケットと通常のチケットの 種類が存在し、どのトッピングにおいてもスペシャルチケット最低 枚を含むチケットの組み合わせでなければ交換できない。

いま、スペシャルチケットを 枚、通常のチケットを 枚持っている。トッピングの価値の合計値を最大化せよ。

解説

ナップザックの亜種、ということで動的計画法を使って解いていきます。説明のため、スペシャルチケットは ST と、通常のチケットは RT と略記します。

dp[i][j][k] := i 番目までのトッピングを使って、ST の残りが j 枚で RT の残りが k 枚である時の価値の最大値 となるように配列を用意します。

どちらの種類のチケットも十分な数あると仮定するとき、 枚のチケットが必要なトッピングに対して使うチケットの組み合わせは 通りありますが、これを全て試していってしまうと DP の更新が 乗ループになり時間的に間に合いません。どこかを工夫して、計算量を落とせないでしょうか？

今回の場合は、ST と RT を組み合わせて 枚使えば良いとのことですので、使うチケットの枚数はどの組み合わせでも等しいです。さらに、いずれのトッピングも ST が最低 枚以上必要であることも重要で、これらを考えると RT の方をなるべく多く使っていけば (ST がなるべく余るように使っていけば) 良いことがわかります。この貪欲で 乗ループになりますので間に合います。計算量は です。

ソースコード

最初メモ化で書こうと思ったけど、意味不明なコードになったので DP で。

int x, y, n;
int t[310], h[310];
int dp[310][310][310];

signed main() {
    cin >> x >> y >> n;
    rep(i,0,n) cin >> t[i] >> h[i];
    memset(dp, 0, sizeof(dp));
    
    rep(i,0,n) repq(j,0,x) repq(k,0,y) {
        dp[i+1][j][k] = dp[i][j][k];
        if(j+k >= t[i] && j != 0) {
            int p, q;
            if(k >= t[i] - 1) {
                p = 1;
                q = t[i] - 1;
            }
            else {
                p = t[i] - k;
                q = k;
            }
            dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j-p][k-q] + h[i]);
        }
    }
    int ans = 0;
    repq(i,0,x) repq(j,0,y) ans = max(ans, dp[n][i][j]);
    cout << ans << endl;
    return 0;
}

さすがにナップザックの亜種は割とできるようになってきたけど、他の DP にもトライしてみなければ・・・。