みんなのプロコン 2019 D問題：Ears

問題. Ears

数直線上を次を満たすように連続的に移動する．
　・移動可能な場所は 0 以上 $L$ 以下
　・整数座標の点からスタートして整数座標の点でゴールする
　・整数座標の点でのみ方向転換可能
整数座標の点 $i$ に対して， $i - 0.5$ を通過すると $s_i$ に1点が加算される．
$A_1, A_2, \ldots, A_L$ が与えられたとき，任意の移動の中で $\sum_{i = 1}^L \left|A_i - s_i \right|$ の最小値を求めよ．

制約： $1 \le L \le 2 \times 10^5$ ，　 $0 \le A_i \le 10^9$

解法．動的計画法

本番で解けなかったので解説を参照しました．
　　みんなのプロコン 2019 予選解説 @DEGwer

スタート，ゴール，訪れた座標の最小値と最大とを決めると 5 つの区間に分割される（各区間は空となるかもしれない）．このとき，スタートとゴールの位置関係によらず， $s_i$ の値は区間ごとに左から 0, 1 以上の任意の偶数，1 以上の任意の奇数，1 以上の任意の偶数，0 とするような移動方法が存在する．したがって，dp[i][j] を $[0, i]$ までを考慮したときに座標 $i$ が 5 つの区間の $j$ 番目に属するときの目的関数値の最小値，として動的計画法を行う．

計算時間： $O(L)$

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

ll Solve() {
    ll l;
    cin >> l;

    vector<ll> a(l + 1);
    for (int i = 1; i <= l; ++i) cin >> a[i];

    constexpr int N = 5;
    vector<vector<ll>> dp(l + 1, vector<ll>(N, 1e11));
    dp[0][0] = 0;

    for (int i = 1; i <= l; ++i) {
        for (int j = 0; j < N; ++j) {
            for (int k = 0; k <= j; ++k) dp[i][j] = min(dp[i][j], dp[i - 1][k]);
            if (j == 0 || j == 4) dp[i][j] += a[i];
            else if (j == 1 || j == 3) dp[i][j] += (a[i] == 0 ? 2 : (a[i] % 2 == 1));
            else if (j == 2) dp[i][j] += (a[i] == 0 ? 1 : (a[i] % 2 == 0));
        }
    }

    return *min_element(dp[l].begin(), dp[l].end());
}

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    cout << Solve() << endl;

    return 0;
}