Common Coupon [第六回 アルゴリズム実技検定 K]

https://atcoder.jp/contests/past202104-open/tasks/past202104_k

前提知識

• 動的計画法

解説

https://atcoder.jp/contests/past202104-open/submissions/22655816

買う買わないの問題。スコアがあって最大化するし、同じ商品は複数買えない。
いかにもDPな感じがするので、とりあえずDPテーブル作れないかを考えてみる。

dp[i] := i番目までを購入したときのスコアの最大値

ここからの遷移を考えると、商品券を発行してもらわないといけないので、少し情報不足。
例えば今まで2021円使ったとするとき、2000円分はすでに商品券が発行されていると考えることができるので、21円が残りになる。
この状況は3021円であっても、3000円分を先に商品券化してスコアに足していけば、21円が残っている状況と変わりない。
よって、購入金額mod100を条件に加えよう。

dp[i][mo] := i番目までを購入していて、購入金額mod100がmoであるようなスコアの最大値（商品券化はしておく）

ここまで考察が進んでいれば、実装はそれほど難しくない。

dp[0][0] = 0;
dp[他][他] = -∞

が初期状態で、

dp[i + 1][mo] ← dp[i][mo] 買わない
dp[i + 1][(mo + P[i]) % 100] ← dp[i][mo] + U[i] - P[i] + (mo + P[i]) / 100 * 20 買う

これでdp[N][any]の最大値が答えとなる。

int N, P[101010], U[101010];
ll dp[101010][101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> P[i] >> U[i];

    rep(i, 0, N + 1) rep(mo, 0, 100) dp[i][mo] = -infl;
    dp[0][0] = 0;
    rep(i, 0, N) rep(mo, 0, 100) {
        chmax(dp[i + 1][mo], dp[i][mo]);
        chmax(dp[i + 1][(mo + P[i]) % 100], dp[i][mo] + U[i] - P[i] + (mo + P[i]) / 100 * 20);
    }

    ll ans = -infl;
    rep(mo, 0, 100) chmax(ans, dp[N][mo]);
    cout << ans << endl;
}