ABC153 E - Crested Ibis vs Monster
備忘録
問題
回答
言語PyPy3 (7.3.0)
で回答
import sys, os, math, bisect, itertools, collections, heapq, queue # from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall from decimal import Decimal from collections import defaultdict # import fractions sys.setrecursionlimit(10000000) ii = lambda: int(sys.stdin.buffer.readline().rstrip()) il = lambda: list(map(int, sys.stdin.buffer.readline().split())) fl = lambda: list(map(float, sys.stdin.buffer.readline().split())) iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)] iss = lambda: sys.stdin.buffer.readline().decode().rstrip() sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split())) isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)] lcm = lambda x, y: (x * y) // math.gcd(x, y) # lcm = lambda x, y: (x * y) // fractions.gcd(x, y) MOD = 10 ** 9 + 7 MAX = float('inf') def main(): if os.getenv("LOCAL"): sys.stdin = open("input.txt", "r") H, N = il() magic = [il() for _ in range(N)] dp = [0] * (H + 1) dp[0] = 0 for h in range(1, H + 1): for n in range(N): if n == 0: if magic[n][0] <= h: dp[h] = dp[h - magic[n][0]] + magic[n][1] else: dp[h] = magic[n][1] else: if magic[n][0] <= h: dp[h] = min(dp[h], dp[h - magic[n][0]] + magic[n][1]) else: dp[h] = min(dp[h], magic[n][1]) print(dp[-1]) if __name__ == '__main__': main()
考え方
動的計画法でモンスターを倒すために必要な最低魔力を求める。
解説は以下がわかりやすかった。
ABC153:問題EでDPの典型問題を復習する。しかし、dpの配列を一次元配列でACすることはまだできていない。|Takahiro Nakamori|note
なお、参考URLは2次元DPで回答しているが、
本記事では1次元DPで回答している。
モンスターの体力をh
としたとき、以下のようなDPを考える。
dp[h] = 体力hをゼロ以下にするために必要な最低魔力量
dp[0]
の時は減らす体力がなければ魔力も必要ないためdp[0] = 0
とし、
dp[1]
から最低1回は魔法を使う必要性があるため、最も魔力を必要としない使い方でDPの更新を行う。
注意点として、dp配列は0
で初期化しているため、魔法の選択肢が1つしかない場合には、
min
が使用できないこと。
魔法の選択肢が2つ目以降は普通にmin
を使用して最低値を選択すればよい。