DP-Bildungswettbewerb B - Frosch 2 , es gibt einen Fall, in dem der folgende Code unweigerlich zu TLE wird, also habe ich ihn bei PyPy eingereicht Es wird leicht AC. Als ich später nachforschte, stellte sich heraus, dass derselbe Algorithmus je nach verwendeter Sprache AC sein kann ( Referenz ). Python-Benutzer sollten PyPy auswählen, es sei denn, sie verwenden eine Bibliothek, die nicht in PyPy implementiert ist. Seien Sie jedoch vorsichtig, da dies viel Speicherplatz beansprucht. Als ich es mit Frog1 ausprobiert habe, verbraucht es mit derselben Quelle ungefähr viermal so viel Speicher.
| Sprache | Erinnerung |
|---|---|
| Python(3.82) | 20524 KB |
| PyPy3 (7.3.0) | 84904 KB |
import sys
sys.setrecursionlimit(250000)
input = sys.stdin.readline
def main():
n, k = map(int, input().split())
h = list(map(int,input().split()))
cost = [sys.maxsize]*n
cost[0] = 0
for i in range(0,n):
for j in range(1, k + 1):
if (i+ j>= n):
break
abs_ = abs(h[i] - h[i+j])
if cost[i+j] >cost[i] + abs_ :
cost[i+j] = cost[i] + abs_
print(cost[n-1])
main()
Recommended Posts