ABC153 E - Crested Ibis vs Monster - 競プロ

ABC153 E - Crested Ibis vs Monster

https://atcoder.jp/contests/abc153/tasks/abc153_e

提出

code: python

h, n = map(int, input().split())

ab = list(map(int, input().split())) for _ in range(n)

# dpi 魔力iの消耗で与えられるダメージの最大値

dp = 0 * (10**4 + 1)

dp0 = 0

解答

code: python

H, N = map(int, input().split())

ab = list(map(int, input().split())) for _ in range(N)

# print(ab)

# 8, 3], 4, 2, [2, 1

# dpi := モンスターの体力をi減らすのにかかる最小コスト

dp = float('inf') * (H + 1)

dp0 = 0

for i in range(H):

for damage, cost in ab:

if i + damage <= H:

# dp8 = min(dp8, dp0+3)...

dpi + damage = min(dpi + damage, dpi + cost)

else:

dpH = min(dpH, dpi + cost)

# print(dp)

# 0, inf, 1, inf, 2, inf, 3, inf, 3, 4

print(dp-1)

テーマ

蟻本 2-3 個数制限なしナップサック問題

メモ

ABC153 E - Crested Ibis vs Monster