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を以下のように定義する。

.cpp

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

遷移は以下。

.cpp

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;
    }
}