Edited at

Educational DP Contest B - Frog 2


問題概要

問題へのリンク

要素数$N$の配列$h$がある。配列の左端(インデックス$0$)から右端(インデックス$n-1$)へ以下の進み方で進む。

点$i$から $i+1,i+2,…,i+K$のどれかへ進む。この時進んだ先の点を$j$とすると、移動コストは $|h_j - h_i|$ である。

総移動コストの最小値を求めよ。


制約条件


  • 入力はすべて整数である。

  • $2≤N≤10^5$

  • $1≤K≤100$

  • $1≤h_i≤10^4$


考えたこと

基本的なDPの問題。

dpを以下のように定義する。

dp[i] == 移動コストの最小値

遷移は以下。

for(int i = 1; i < n; i ++) {

dp[i] = min(dp[i],abs(h[i]-h[i-j]) + dp[i-j]); //(1≤j≤100)
}

計算量は $O(NK)$。

小さいことですがlong型で提出しないとREなっちゃいます...(原因がわからなくて3回REかましちゃいました...)


解答

C++


b.cpp

#include <bits/stdc++.h>

using namespace std;

int main() {
int n,k; cin >> n >> k;
vector<long> h(n);
for(int i = 0; i < n; i ++) cin >> h[i];
vector<long> dp(n);
dp[0] = 0;
for(int i = 1; i < n; i ++) {
for(int j = 1; j <= min(i,k); j ++) {
if(j==1) dp[i] = abs(h[i]-h[i-j]) + dp[i-j];
else dp[i] = min(dp[i],abs(h[i]-h[i-j]) + dp[i-j]);
}
}
cout << dp[n-1] << endl;
}


C#


b.cs

using System;

using System.Linq;

class Program
{
static void Main(string[] args) {
int[] nk = Console.ReadLine().Split().Select(int.Parse).ToArray();
long[] h = Console.ReadLine().Split().Select(long.Parse).ToArray();
Console.WriteLine(dp(nk[0],nk[1],h)[nk[0]-1]);
}
static long[] dp(int n, int k, long[] h) {
long[] dp = new long[n];
dp[0] = 0;
for(int i = 1; i < n; i ++) {
for(int j = 1; j <= Math.Min(k,i); j ++) {
if(j==1) dp[i] = Math.Abs(h[i]-h[i-j]) + dp[i-j];
else dp[i] = Math.Min(dp[i], Math.Abs(h[i]-h[i-j]) + dp[i-j]);
}
}
return dp;
}
}