E No quantity knapsack problem. It was constructed recursively, but TLE without considering the amount of calculation. I didn't know how to make dp using an array, so the time was up.
Commentary on youtube https://www.youtube.com/watch?v=pHzHTVIqrG8&feature=youtu.be
Hitpoint, N = map(int, input().split())
magic_damage = []
magic_point = []
for _ in range(N):
A, B = map(int, input().split())
magic_damage.append(A)
magic_point.append(B)
# dp = [[float("inf") for _ in range(Hitpoint + 1)] for _ in range(N + 1)]
dp = [float('inf') for _ in range(Hitpoint + 1)]
dp[0] = 0
for i in range(N):
for now_HP in range(Hitpoint + 1):
next_HP = min(now_HP + magic_damage[i], Hitpoint)
dp[next_HP] = min(dp[next_HP], dp[now_HP] + magic_point[i])
# dp[i + 1][now_HP] = min(dp[i + 1][now_HP], dp[i][now_HP - magic_damage[i]] + magic_point[i])
print(dp[Hitpoint])
Recommended Posts