Pythonで毎日AtCoder #40

はじめに

前回
今日はDPContestのA~Cをやります

A問題

問題

考えたこと
dp[i]は$dp[i-1]+abs(h[i]-h[i-1]) or dp[i-2]+abs(h[i]-h[i-2])$になります。この二つの最小値を更新していって求めます。

n = int(input())
h = list(map(int,input().split()))

dp = [0] * n  #infの方がいい気がする

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])

B問題

問題

考えたこと
Aと違うのは選択肢がふたつからK個になったことですが、その分minを取る部分を増やすだけです。

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])

C問題

問題

考えたこと
A,Bと違ってdp[i-1]がdp[i]の選択肢に関わってきます。ですので、dp[i-1]でなにを選んだのかを記録するためにdp[i][j]というようにdpの要素を一つ増やします。あとは、選択肢の3つ全て計算して最大値を取ります。

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)

まとめ

dpって名前がかっこいいですよね。使いこなせるようにがんばります。明日のABCがんばりましょう!
ではまた、おやすみなさい。