ABC153 E - Crested Ibis vs Monster
問題原文
問題要旨
体力が のモンスターがいる。
種類の魔法が使えて、魔法 は、モンスターの体力を 減らすことができるが、 魔力を 消費する。
同じ魔法を何度でも使える時、モンスターの体力を0以下にするためには、最小でどのぐらいの魔力がいるか?
解法
どう考えてもDPの雰囲気しかしない。というかDPド典型。
として、あとは個数制限なしナップサックと同じ。
計算量は 。ステップ数が 程度になってちょっとビクっとするけど流石に余裕で通る。
実装
を超える部分はまとめてあげると楽。
Magic = [list(map(int, input().split())) for i in range(N)] MAX_COST = max(Magic)[1] # dp[damage] := モンスターに damage を与えるために必要な最小コスト dp = [float('inf')] * (H + 1) dp[0] = 0 for h in range(H): for damage, cost in Magic: next_index = min(h + damage, H) dp[next_index] = min(dp[next_index], dp[h] + cost) print(dp[-1])
感想
瞬殺できてよかった。
DPの基礎問としてちょうどいいかも。