【Educational DP Contest】EDPC-B-Frog2【Python】

問題
解答
1. 方針
2. 解答
その他
1. 解答・解説記事一覧

問題

B – Frog 2 (atcoder.jp)

解答

方針

dp[i]：i番目の足場でのコストの最小値

遷移式：dp[i] = min(dp[i],dp[i-j]+abs(H[i]-H[i-j]))

解答

コード・コメント

#入力
n,k = map(int,input().split())
H = list(map(int,input().split()))

#最小値を求めるのでDP配列は無限大で初期化
dp = [float("inf")]*n
#DP配列の1番目の要素を0とする
dp[0] = 0
#2番目以降の足場の数だけ繰り返す
for i in range(1,n):
    #2番目の足場の場合
    if i == 1:
        #1番目の足場と2番目の足場の高さを記録
        dp[i]=abs(H[i]-H[0])
    #3番目以降の足場の場合
    else:
        #ある足場からk個まで飛べる → 足場iには、足場(i-k)～足場(i-1)のそれぞれから飛んでくることができるので、k回繰り返す
        for j in range(1,k+1):  
            #iよりもjが大きい場合、1番目の足場よりもさらに手前の足場から飛んできたことになるが、実際は1番目の足場より手前には足場はないため、iがj以上の場合のみ計算する。(ここがなくともなぜかACした)
            if i>=j:
                #dp[i]は最初は無限大。足場(i-j)個から足場iへ飛んできたときに、そのコストが今よりも小さければ更新
                dp[i]=min(dp[i],dp[i-j]+abs(H[i]-H[i-j]))
#最後の足場のコストを出力
print(dp[-1])

#入力

n,k = map(int,input().split())

H = list(map(int,input().split()))

#最小値を求めるのでDP配列は無限大で初期化

dp = [float("inf")]*n

#DP配列の1番目の要素を0とする

dp[0] = 0

#2番目以降の足場の数だけ繰り返す

for i in range(1,n):

#2番目の足場の場合

if i == 1:

#1番目の足場と2番目の足場の高さを記録

dp[i]=abs(H[i]-H[0])

#3番目以降の足場の場合

else:

#ある足場からk個まで飛べる → 足場iには、足場(i-k)～足場(i-1)のそれぞれから飛んでくることができるので、k回繰り返す

for j in range(1,k+1):

#iよりもjが大きい場合、1番目の足場よりもさらに手前の足場から飛んできたことになるが、実際は1番目の足場より手前には足場はないため、iがj以上の場合のみ計算する。(ここがなくともなぜかACした)

if i>=j:

#dp[i]は最初は無限大。足場(i-j)個から足場iへ飛んできたときに、そのコストが今よりも小さければ更新

dp[i]=min(dp[i],dp[i-j]+abs(H[i]-H[i-j]))

#最後の足場のコストを出力

print(dp[-1])

コード

n,k = map(int,input().split())
H = list(map(int,input().split()))

dp = [float("inf")]*n
dp[0] = 0
for i in range(1,n):
    if i == 1:
        dp[i]=abs(H[i]-H[0])
    else:
        for j in range(1,k+1):  
            if i>=j:
                dp[i]=min(dp[i],dp[i-j]+abs(H[i]-H[i-j]))
print(dp[-1])

n,k = map(int,input().split())

H = list(map(int,input().split()))

dp = [float("inf")]*n

dp[0] = 0

for i in range(1,n):

if i == 1:

dp[i]=abs(H[i]-H[0])

else:

for j in range(1,k+1):

if i>=j:

dp[i]=min(dp[i],dp[i-j]+abs(H[i]-H[i-j]))

print(dp[-1])

その他

解答・解説記事一覧

EDPCの解答・解説記事一覧

【Python】Educational DP Contest 解答・解説記事一覧【EDPC】

ABCの解答・解説記事一覧

【Python】AtCoder Beginner Contest 解答・解説記事一覧