ABC153 E - Crested Ibis vs Monster

問題原文

atcoder.jp

問題要旨

体力が のモンスターがいる。
種類の魔法が使えて、魔法 は、モンスターの体力を 減らすことができるが、 魔力を 消費する。
同じ魔法を何度でも使える時、モンスターの体力を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の基礎問としてちょうどいいかも。