Letztes Mal Heute werde ich A ~ C des DP-Wettbewerbs machen
** Gedanken ** dp [i] ist $ dp [i-1] + abs (h [i] -h [i-1]) oder dp [i-2] + abs (h [i] -h [i-2]) $ Wird sein. Sie wird berechnet, indem diese beiden Mindestwerte aktualisiert werden.
n = int(input())
h = list(map(int,input().split()))
dp = [0] * n #Ich finde, dass inf besser ist
for i in range(1,n):
if i == 1:
dp[i] = abs(h[i]-h[0])
continue
dp[i] = min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]))
print(dp[-1])
** Gedanken ** Der Unterschied zu A besteht darin, dass sich die Anzahl der Auswahlmöglichkeiten von zwei auf K geändert hat, aber nur der Teil, der min benötigt, entsprechend erhöht wird.
n, k = map(int,input().split())
h = list(map(int,input().split()))
dp = [float('inf')] * n
dp[0] = 0
dp[1] = abs(h[1]-h[0])
for i in range(2,n):
for j in range(k+1):
if i - j < 0:
continue
dp[i] = min(dp[i-j]+abs(h[i]-h[i-j]),dp[i])
print(dp[-1])
** Gedanken ** Im Gegensatz zu A und B ist dp [i-1] an der Wahl von dp [i] beteiligt. Fügen Sie also ein Element von dp wie dp [i] [j] hinzu, um aufzuzeichnen, was Sie mit dp [i-1] ausgewählt haben. Berechnen Sie danach alle drei Optionen und nehmen Sie den Maximalwert.
n = int(input())
abc = [list(map(int,input().split())) for _ in range(n)]
dp = [[0 for _ in range(3)] for _ in range(n+1)]
for i in range(1,n+1):
for j in range(3):
for k in range(3):
if j == k:
continue
dp[i][k] = max(dp[i][k],dp[i-1][j] + abc[i-1][k])
ans = 0
for i in range(3):
ans = max(ans,dp[n][i])
print(ans)
Der Name dp ist cool, nicht wahr? Ich werde mein Bestes geben, um es zu meistern. Lassen Sie uns morgen unser Bestes geben, ABC! Wir sehen uns wieder, gute Nacht.
Recommended Posts