AtCoder Beginner Contest D - Redistribution Difficulty: 830
Dieses Thema, dynamische Planungsmethode
Dies ist ein sogenanntes typisches dynamisches Planungsproblem.
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
Diesmal ist es in Ordnung, also füge dp nur für i + x <= s hinzu.
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 *** ist wirklich schnell, nicht wahr?
| Ruby | Python | PyPy | |
|---|---|---|---|
| Codelänge(Byte) | 244 | 405 | 405 |
| Ausführungszeit(ms) | 284 | 509 | 70 |
| Erinnerung(KB) | 14400 | 9060 | 64596 |
Referenzierte Site
Recommended Posts