AtCoder Beginner Contest E - Crested Ibis vs Monster Difficulty: 1009
Ce thème, méthode de planification dynamique
Il s'agit d'un problème de planification dynamique dit typique. Trouvez la puissance magique totale minimale que Toki consomme avant de gagner un monstre. Cependant, veuillez noter qu'il n'est pas nécessaire qu'il soit "0" simplement en rendant la force physique du monstre "0 ou moins".
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
À ʻelsif i + x> = h, il est fixé à dp [h]` comme traitement lorsque la force physique du monstre devient "0 ou moins".
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()
Si vous n'êtes pas *** PyPy ***, ce sera «TLE».
| Ruby | Python | PyPy | |
|---|---|---|---|
| Longueur du code(Byte) | 336 | 476 | 476 |
| Temps d'exécution(ms) | 1630 | TLE | 399 |
| Mémoire(KB) | 2044 | 3616 | 41452 |
Recommended Posts