AtCoder Beginner Contest E - Crested Ibis vs Monster Difficulty: 1009
Dieses Thema, dynamische Planungsmethode
Dies ist ein sogenanntes typisches dynamisches Planungsproblem. Finde die minimale magische Gesamtkraft, die Toki verbraucht, bevor du ein Monster gewinnst. Bitte beachte jedoch, dass es nicht "0" sein muss, nur indem die physische Stärke des Monsters auf "0 oder weniger" gesetzt wird.
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
Bei "elsif i + x> = h" wird "dp [h]" als Verarbeitung festgelegt, wenn die physische Stärke des Monsters "0 oder weniger" wird. 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()
Wenn Sie nicht *** PyPy *** sind, wird es TLE sein.
| Ruby | Python | PyPy | |
|---|---|---|---|
| Codelänge(Byte) | 336 | 476 | 476 |
| Ausführungszeit(ms) | 1630 | TLE | 399 |
| Erinnerung(KB) | 2044 | 3616 | 41452 |
Recommended Posts