ABC153 E - Crested Ibis vs Monster - ツバサの備忘録

解法

$dp[i][j] = i$ 番目までの魔法を撃ち終えて、 $j$ だけダメージを与えたときに消費する魔力の最小値
とすると、

$j \geqq A_{i}$ のとき
$dp[i +1][j] = min(dp[i][j],dp[i + 1][j - A_{i}] + B_{i})$
$j \lt A_{i}$ のとき
$dp[i + 1][j] = dp[i][j]$

となります。
初期値は $dp[0][0] = 0$ 、答えは、 $min(dp[N][j]) (j \geqq H)$ です。
見るべき $j$ の範囲は、 $H + max(A_{i})$ までなので、最大でも $2 \times 10^{4}$ 程度になり、このDPによる計算が間に合います。
これが提出コード(2)です。

$dp[i][j] = i$ 番目までの魔法を撃ち終えて、 $j$ 以上ダメージを与えたときに消費する魔力の最小値
とすると、
$dp[i + 1][j] = min(dp[i][j],dp[i + 1][max(0,j-A_{i})] + B_{i})$

となります。初期値は上と同様、答えは $dp[N][H]$ です。
これが提出コード(1)になります。