パンケーキ [パソコン甲子園2016 予選 F]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0340?year=2016

前提知識

• 動的計画法 （想定解では貪欲で解けるので、必要不可欠ではない）

考察過程

1. pの上限が小さいのが気になる
2. 裏返しの操作は順番が逆になっても結果が変わらない
3. 先頭から順番に裏返し操作をしていくことにすると、後半に影響してくるのは操作し終わった最後の要素のみ
4. pの上限も少ないので、DPできる

解法

https://onlinejudge.u-aizu.ac.jp/solutions/problem/0340/review/3140080/hamayanhamayan/C++14

※ 想定解は貪欲法です
　
dpで解こう。
dp[idx][last] := idx番目まで処理が終わっていて、最後の要素にパンケーキがlast分残っているときのパンケーキの総裏返し回数のmin
左端の裏返しだけ1つのみで行えるので、別途DPを作る。
あとの遷移は次のパンケーキをlast2個残すというので遷移させる。
残すために必要な裏返し回数をdとすると、last≦dを満たす必要がある。
そうじゃないと、1つ前のパンケーキが必要な裏返し回数を満たさないためである。
あとは、最後に残ったパンケーキの裏返しを考慮して最小のものを取ると答え。

int N, P[5010];
int dp[5010][4];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> P[i];

    rep(idx, 0, 5010) rep(last, 0, 4) dp[idx][last] = inf;
    rep(last, 0, P[0] + 1) dp[0][last] = P[0] - last;

    rep(idx, 0, N - 1) rep(last, 0, 4) {
        rep(last2, 0, P[idx + 1] + 1) {
            int d = P[idx + 1] - last2;
            if (d < last) continue;

            chmin(dp[idx + 1][last2], dp[idx][last] + d * 2);
        }
    }

    int ans = inf;
    rep(last, 0, 4) chmin(ans, dp[N - 1][last] + last);
    cout << ans << endl;
}