AtCoder ABC 153 E - Crested Ibis vs Monster

$dp[i][k]$ = $i$ 番目までの魔法からダメージが $k$ 以上になるように選んだ時に消費するMPの最小値

とすると、個数制限なしナップザック問題（の類似）に帰着される。 (参考:蟻本の2章 p.p.58 漸化式を工夫する)

$dp[i+1][k] = \min(dp[i][k], dp[i+1][k-a[i]]+b[i])$

である。ここで、 $dp[-1][k] = 0$ と $dp[i][k] = 0 \ (k < 0)$ とおいた。

答えは $dp[n][h]$ であり、 $O(nh)$ で求められる。