[AtCoder] ABC 153 E – Crested Ibis vs Monster

問題

方針

商品を無数に選ぶことができるナップザック問題なので、動的計画法を使って解きます。\( d(i) \) をモンスターに \( i \) ダメージ与えれるために必要な魔力とします。初期値は、\( d(0) = 0 \) であり、\( d(i) = \infty \ (i \neq 0) \) とします。

更新式は、\( d(i + A_j) = \min(d(i + A_j), d(i) + B_j) \ (1\leq j \leq N)\) です。注意として、\( d(H) = \infty \) となることがあるので、\( d(i) \ (H \leq i) \) を満たす \( i \) について最小値を探します。

方針