Dernière fois Aujourd'hui, je vais faire A ~ C du concours DP
** Pensées ** dp [i] est $ dp [i-1] + abs (h [i] -h [i-1]) ou dp [i-2] + abs (h [i] -h [i-2]) $ Sera. Il est calculé en mettant à jour ces deux valeurs minimales.
n = int(input())
h = list(map(int,input().split()))
dp = [0] * n #Je sens que c'est mieux
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])
** Pensées ** La différence avec A est que le nombre de choix est passé de deux à K, mais seule la partie qui prend min est augmentée en conséquence.
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])
** Pensées ** Contrairement à A et B, dp [i-1] est impliqué dans le choix de dp [i]. Alors, ajoutez un élément de dp comme dp [i] [j] pour enregistrer ce que vous avez choisi avec dp [i-1]. Après cela, calculez les trois options et prenez la valeur maximale.
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)
Le nom dp est cool, non? Je ferai de mon mieux pour le maîtriser. Faisons de notre mieux l'ABC de demain! A bientôt, bonne nuit.
Recommended Posts