【競プロ】1日1AC : EDPC A, B問題【動的計画法】

競プロをするにあたって、便利なアルゴリズムを使えるようになることは重要です。そんなわけで、今日からしばらくDP（動的計画法）に関する問題を解いていきます。

問題はAtCoderのEducational DP Contestのものを使います。

簡単な問題から始まるので、競プロを始めたばかりの人も一緒に解き進めていきましょう。（そもそもDPって何だ？と思うかもしれませんが、知らなくても問題を見れば十分雰囲気が掴めると思います。）

1 A問題
2 B問題
3 終わりに

A問題

提出コードと説明を合わせるために足場には \( 0,1,2, \cdots ,N-1 \) の番号が振られているとします。

いきなりですが \( dp_i \) を足場 \( i \) に行くまでの最小コストとします。足場 \( i \) へは、足場 \( i-1 \) か \( i-2 \) から移ることができます。それぞれの足場へ行くための最小コスト \( dp_{i-1},dp_{i-2} \) が考えられるので、

\[ dp_i=\min \{dp_{i-1}+|h_i-h_{i-1}|,dp_{i-2} + |h_i-h_{i-2}|\} \]

が成り立ちますね。

以下が提出コードです。
（この問題の場合は関係ないのですが、DPを用いて何かしらの最小値を求める時は大きな数(INF)で配列を初期化するのが普通なようなので、ここでもそうしています。）

#include <bits/stdc++.h>
using namespace std;

const long long INF = 1LL << 60;

int main(){
    int N;
    cin >> N;
    vector<int> h(N);
    for(int i = 0;i < N;i++) cin >> h[i];

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

\(\mathrm{abs}(a)\) は \(|a|\) と同じです。

なんとなくイメージが掴めたでしょうか。

B問題

\(K=2\) の場合がA問題です。\(dp_i\)を先程の定義と同じにすると、

\[ dp_{i}=\min \{ 1\leq j \leq K \mid dp_{i-j}+|h_i-h_{i-j}| \} \]

とすればいいでしょう。ごちゃごちゃしてますが足場 \(i\) に行く \(K\) 通りのうち、コストが最小になるものを \(dp_i \) としています。先ほどと同じですね。

実装の都合上、先程の式は次の形の方が扱いやすいでしょう。

\[ dp_{i+j}=\min \{ 1\leq j \leq K \mid dp_{i}+|h_{i+j}-h_{i}| \} \]

以下が提出コードです。

#include <bits/stdc++.h>
using namespace std;

const long long INF = 1LL << 60;

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

\(i+j\) が \(N-1\) を超えることがあるのでループを途中で止めるか、面倒なら上のように配列の要素を多めに取っておいてもいいと思います。