読者です 読者をやめる 読者になる 読者になる

hogecoder

つたじろう(Tsuta_J) 競技プログラミングの記録

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

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

問題概要

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

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

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

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

解説

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

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

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

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

ソースコード

最初メモ化で書こうと思ったけど、意味不明なコードになったので 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 にもトライしてみなければ・・・。