Posted at

Educational DP Contest A - Frog 1


問題概要

問題のリンク

要素$N$個の配列$h$がある。

点$1$からスタートして$N$にたどり着くまで移動する。ある点$i$からは$i+1$または$i+2$に移動することができる。

移動先の点を$j$とすると、$|h_j - h_i|$が移動コストとなる。移動コストの最小値を求めよ。


制約条件


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

  • $2≤N≤10^5$

  • $1≤h_i≤10^4$


考えたこと

まんまこれでびっくりした。 → C - 柱柱柱柱柱

前やったときのを思い出しながら解いた。

点$i$における最適値(=最小値)は1個前か2個前の値に依存する。仮に点$i$において1個前の値が最適値になるのであれば、その$i-1$の値は1個前と2個前のどちらかに依存しているかが問題となってくる。

これを逐次保存して管理していくことにより計算量を抑える。

遷移式は以下のようになる。

初項と第一項は自明で第二項以降は1個前か2個前どちらの値に最適値が依存しているかを判定していく。

vector<int> dp(n);

dp[0] = 0;
dp[1] = abs(h[1]-h[0]);
for(int i = 2; i < n; i ++) {
dp[i] = min(abs(h[i]-h[i-1]) + dp[i-1], abs(h[i]-h[i-2]) + dp[i-2]);
}

計算量は $O(N)$です。


解答

C#の解答

using System;

using System.Linq;

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

C++の解答

#include <bits/stdc++.h>

using namespace std;

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