ABC 153-E

競プロ DP

問題見てしばらくしてdpというのは分かった。しかしコードを書き上げてもなかなかバグが取れない。

for(int i=h;i>=0;i--){

   for(int j=0;j<n;j++){

   }

}

という二重ループを回し、

dp[i][j]:現在モンスターの体力がiで、魔法jを使おうとしてるときに、今までに消費した魔力の合計の最小値

と考えたが、遷移の際にdpテーブルに魔力の情報は必要ない(むしろバグる)と分かったので、以下のように書き換えた。

dp[i]:現在のモンスターの体力がiのときに今まで消費した魔力の合計の最小値

ただしモンスターの体力がその値を取りうるかどうかを確認しなければならないので注意が必要。