AtCoder Beginner Contest E - Crested Ibis vs Monster Difficulty: 1009
This theme, dynamic programming
It is a problem of so-called typical dynamic programming.
Find the minimum total amount of magical power that Toki consumes before winning a monster.
However, please note that it does not have to be 0 just by making the monster's physical strength 0 or less.
Ruby
ruby.rb
h, n = gets.split.map(&:to_i)
a = Array.new(n){gets.split.map(&:to_i)}
dp = Array.new(h + 1, Float::INFINITY)
dp[0] = 0
h.next.times do |i|
a.each do |x, y|
if i + x < h && dp[i + x] > dp[i] + y
dp[i + x] = dp[i] + y
elsif i + x >= h && dp[h] > dp[i] + y
dp[h] = dp[i] + y
end
end
end
puts dp[h]
ruby.rb
if i + x < h && dp[i + x] > dp[i] + y
dp[i + x] = dp[i] + y
elsif i + x >= h && dp[h] > dp[i] + y
dp[h] = dp[i] + y
end
At ʻelsif i + x> = h, it is fixed to dp [h]as the processing when the monster's physical strength becomes0 or less`.
Python
pypy.py
from sys import stdin, maxsize
def main():
input = stdin.readline
h, n = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
dp = [maxsize] * (h + 1)
dp[0] = 0
for i in range(h + 1):
for x, y in a:
if i + x < h and dp[i + x] > dp[i] + y:
dp[i + x] = dp[i] + y
elif i + x >= h and dp[h] > dp[i] + y:
dp[h] = dp[i] + y
print(dp[h])
main()
If you are not *** PyPy ***, it will be TLE.
| Ruby | Python | PyPy | |
|---|---|---|---|
| Code length(Byte) | 336 | 476 | 476 |
| Execution time(ms) | 1630 | TLE | 399 |
| memory(KB) | 2044 | 3616 | 41452 |
Recommended Posts