[学習記録]AtCoder EDP B-Frog 2[Go]
問題文
N 個の足場があります。 足場には 1,2,…,N と番号が振られています。 各 i (1≤i≤N) について、足場 i の高さは hi です。
最初、足場 1 にカエルがいます。 カエルは次の行動を何回か繰り返し、足場 N まで辿り着こうとしています。
足場 i にいるとき、足場 i+1,i+2,…,i+K のどれかへジャンプする。 このとき、ジャンプ先の足場を j とすると、コスト∣hi−hj∣ を支払う。
カエルが足場 N に辿り着くまでに支払うコストの総和の最小値を求めてください。
解法
基本的にはA-Frog 1 と同じ解法でいけるが、ジャンプできる足場の数がK個あるので、ここをループによって求める。
i - j < 0 となったとき、足場が存在しないため、ループを終了する
for i := 1; i < n; i++ {
for j := 1; j <= k; j++ {
if i-j < 0 {
break
}
dp[i] = Min(dp[i-j]+Abs(sli[i-j]-sli[i]), dp[i])
// same as below
// before := dp[i-j] + Abs(sli[i-j] - sli[i])
// dp[i] = Min(before, dp[i])
}
}
dpが0で初期化されているため、このままだと必ずMin(before, dp[i]) = 0となり、計算できない。そのため、ガードを入れることで計算を続行する
if dp[i] == 0 {
dp[i] = dp[i-1] + Abs(sli[i-1]-sli[i])
continue
}
Frog 1 と同様に、dp[n -1]が答えになる
コード(AC)
func run() interface{} {
n, k := readInt(), readInt()
sli := readSli(n)
dp := make([]int, n)
for i := 1; i < n; i++ {
for j := 1; j <= k; j++ {
if i-j < 0 {
break
}
if dp[i] == 0 {
dp[i] = dp[i-1] + Abs(sli[i-1]-sli[i])
continue
}
dp[i] = Min(dp[i-j]+Abs(sli[i-j]-sli[i]), dp[i])
}
}
ans := dp[n-1]
return ans
}
この記事が気に入ったらサポートをしてみませんか?