Crested Ibis vs Monster [AtCoder Beginner Contest 153 E]

https://atcoder.jp/contests/abc153/tasks/abc153_e

前提知識

• 動的計画法

解説

https://atcoder.jp/contests/abc153/submissions/9783902

制約と最小化でDPかなという感じがする。
雑な初手であるが、DPをむちゃくちゃやったらこういう思考になる。
10³というのは微妙な制約であり、O(N²)が回る。
そして、体力と魔力の関係を見ると、ナップサック問題な印象を受ける。
言い訳はこれくらいでいいか。

DPであることが分かれば、DPテーブルは立てやすいかもしれない。
dp[i][h] := i番目の魔法まで使い終わって、残りの体力がhであるときの、消費魔力の最小値

自然な遷移として、
魔法を使わない dp[i][h] -> dp[i+1][h] の遷移と、
魔法を1回使う dp[i][h] -> dp[i+1][h-A[i]] の遷移が思いつくだろう。

ここまではあまり難しくないのだが、ここから始めて体験する場合は難しく感じるだろう。
今回の問題では、魔法を何回でも使用することができる。
よって、i番目の魔法を使ったとしても、再度i番目の魔法が使いたくなる。
遷移を dp[i][h] -> dp[i][h-A[i]] として考える。
この遷移が問題ないかを考えて見る。
DPの遷移で重要なのが、遷移関係がDAGを成すという部分である。
通常のDPであれば、i<i+1で必ず方向が定まるのでいい。
今回のDPであれば、それに加えて、hの方の遷移は数が小さくなる。
数が小さくなるのであれば、順序関係が定まり、DAGを成すということである。
まあ、この辺の理解はふんわりできてればいいので、ループが無いなくらいの確認でもいい。

まとめると、遷移は、
魔法を使わない dp[i][h] -> dp[i+1][h] の遷移と、
魔法を1回使う dp[i][h] -> dp[i][h-A[i]] の遷移を行えばいい。
DPの更新順序に注意する必要がある。
iは昇順に更新するが、hは大きい数から確定していくので、降順で更新しよう。

int H, N, A[1010], B[1010];
int dp[1010][10101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> N;
    rep(i, 0, N) cin >> A[i] >> B[i];

    rep(i, 0, N + 1) rep(h, 0, H + 1) dp[i][h] = inf;
    dp[0][H] = 0;

    rep(i, 0, N) rrep(h, H, 0) {
        chmin(dp[i + 1][h], dp[i][h]);
        chmin(dp[i][max(0, h - A[i])], dp[i][h] + B[i]);
    }

    cout << dp[N][0] << endl;
}