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

問題

 ある飲食店ではN種類のトッピングを行うことができる。トッピングiを入手したときに得られる嬉しさはh_iであり、t_i枚のチケットを使うと入手できるが、その中には1枚以上スペシャルチケットを含んでいる必要がある。同じトッピングを複数回入手することはできない。最初持っているスペシャルチケットをX枚、普通のチケットをY枚として与えるので、嬉しさの最大値を求めよ。

解法

 「 dp[i][j][k] = i番目のトッピングまで考えたときに、残りのスペシャルチケットがj枚、普通のチケットがk枚であるときの嬉しさの最大値」としてテーブルを埋めていけばよい。交換するときまずスペシャルチケットは1枚消費し、それ以外はできるだけ普通のチケットを消費し、まだ足りなかったらスペシャルチケットを消費することが最善なのでO(1)で遷移できる。

反省

 12分25秒(0WA)でAC。パッと見でDPだろうなという感じだったし、遷移が簡単なので慣れていないforループでもそこまで時間がかからず実装できた。これくらいのDPはサッと解けるようにしておきたい。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll X, Y, N;
    cin >> X >> Y >> N;
    vector<ll> t(N), h(N);
    for (ll i = 0; i < N; i++) {
        cin >> t[i] >> h[i];
    }

    vector<vector<vector<ll>>> dp(N + 1, vector<vector<ll>>(X + 1, vector<ll>(Y + 1, 0)));
    for (ll i = 0; i < N; i++) {
        for (ll j = 0; j <= X; j++) {
            for (ll k = 0; k <= Y; k++) {
                //交換する
                ll nk = max(k - (t[i] - 1), (ll)0);
                ll nj = j - (t[i] - (k - nk));
                if (nj >= 0) {
                    dp[i + 1][nj][nk] = max(dp[i + 1][nj][nk], dp[i][j][k] + h[i]);
                }

                //交換しない
                dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k]);
            }
        }
    }

    ll ans = 0;
    for (ll j = 0; j <= X; j++) {
        ans = max(ans, *max_element(dp[N][j].begin(), dp[N][j].end()));
    }
    cout << ans << endl;
}