問題
ある飲食店では種類のトッピングを行うことができる。トッピングを入手したときに得られる嬉しさはであり、枚のチケットを使うと入手できるが、その中には1枚以上スペシャルチケットを含んでいる必要がある。同じトッピングを複数回入手することはできない。最初持っているスペシャルチケットを枚、普通のチケットを枚として与えるので、嬉しさの最大値を求めよ。
解法
「 = 番目のトッピングまで考えたときに、残りのスペシャルチケットが枚、普通のチケットが枚であるときの嬉しさの最大値」としてテーブルを埋めていけばよい。交換するときまずスペシャルチケットは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; }