問題
体力 $H$ のモンスターがいる。トキは $N$ 種類の魔法が使えて、$i$ 番目の魔法はモンスターの体力を $A_i$ 減らせるが、自分の魔力を $B_i$ 消耗する。モンスターの体力を $0$ 以下にするために必要な魔力の消耗の最小値を求める。
解法
動的計画法で求めます。わからない人は「ナップザック問題」でググりましょう。DPまとめコンテストの次の問題あたりが典型例です。
E - Knapsack 2
体力から考える
けんちょんさんの解説がわかりやすいです。ここでは割愛します。
魔力から考える
$dp[i][j]$ = ( $i$ 番目までの魔法を使い、魔力消耗 $j$ で減らせるモンスターの体力)
というDPテーブルを作ります。漸化式は、
dp[i][j] = \max(dp[i-1][j], dp[i][j-B[i]]+A[i])
とします。答えは、あまり直観的ではないですが $\min_{dp[N][j]\geq H}j$ です。
DPテーブルのとり方を工夫する
素朴な問題であれば、上の漸化式をそのまま実装すればACするのですが、今回の問題ではREします。なぜなら、DPテーブルの空間計算量が $O(NH\max A_i) \sim O(10^{11})$ になるためです1。
しかし、よく漸化式を見てみると、$dp[i-1][]$ と $dp[i][]$ の2行しか必要としていません。というわけで、次元を一つ減らして
dp[j] = \max(dp[j], dp[j-B[i]]+A[i])
としても結果に影響が出ないことがわかります。これならば $O(10^8)$ で収まるので、実装可能です2。
感想
半年ぶりくらいにDPを書いたので思い出すのに1時間くらいかかった。