AtCoder Beginner Contest D - Redistribution Difficulty: 830
Ce thème, méthode de planification dynamique
Il s'agit d'un problème de planification dynamique dit typique.
ruby.rb
s = gets.to_i
dp = Array.new(s.next, 0)
dp[0] = 1
s.times do |i|
next if dp[i].zero?
3.upto(s) do |x|
if i + x <= s
dp[i + x] += dp[i]
dp[i + x] %= 1000000007
else
break
end
end
end
puts dp[s]
ruby.rb
if i + x <= s
dp[i + x] += dp[i]
dp[i + x] %= 1000000007
else
break
end
Cette fois c'est très bien, alors ajoutez dp uniquement pour ʻi + x <= s`. Python
python.py
from sys import stdin
def main():
input = stdin.readline
s = int(input())
dp = [0] * (s + 1)
dp[0] = 1
for i in range(s):
if dp[i] == 0:
continue
for x in range(3, s + 1):
if i + x <= s:
dp[i + x] += dp[i]
dp[i + x] %= 1000000007
else:
break
print(dp[s])
main()
*** PyPy *** est vraiment rapide, n'est-ce pas?
| Ruby | Python | PyPy | |
|---|---|---|---|
| Longueur du code(Byte) | 244 | 405 | 405 |
| Temps d'exécution(ms) | 284 | 509 | 70 |
| Mémoire(KB) | 14400 | 9060 | 64596 |
Site référencé
Recommended Posts