Laminate [AtCoder Beginner Contest 145 F]

https://atcoder.jp/contests/abc145/tasks/abc145_f

必要知識

• 座標圧縮
• 動的計画法

解説

https://atcoder.jp/contests/abc145/submissions/8491333

必要な知見として高さを操作するが、最初に与えられているHiの高さにするか0にするかしかない。
中途半端なものに変更しても旨味がない。
あとは、Nの制約がとても小さいため、dp[300][300][300]かなーと思って考えるとDPが出てくる。

DP[i][k][h] := i行目までで、k回操作を行っていて、最後の列の高さがhである場合の必要な操作回数
DP[i][k][h]からdp[i+1][k+1][h2]への遷移ではh2≦hであれば追加コストはかからない。
これは、元々ある操作の一部を一列分拡張すればいいからである。
h<h2であればコストが差分だけかかる。
hは座標圧縮しないと状態数が足りない。

遷移が3つあるので、3つに分けて遷移させよう。

先にH[i]=hを片付けよう。
DP[i+1][k][h] = min(DP[i][k][全てのh]+max(0,H[i]-h)

DP[i][k][h]からdp[i+1][k+1][h2]への遷移では、h2≦hとなっている。
追加コストがかからないので、DP[i+1][k+1][h2] = min(DP[i][k][h2より大きい])
逆順で更新して、順番に最小値を持っていれば更新可能

h<h2の場合。
DP[i+1][k+1][h] = min(DP[i][k][h未満] + hとh未満の差)
差の計算が難しいが、結果は伝播させることができる。
実は、DP[i+1][k+1][h] = min(DP[i][k][h-1] + hとh-1の差, DP[i+1][k+1][h-1] + hとh-1の差)とできる。
これは
DP[i+1][k+1][h] = min(DP[i][k][h未満] + hとh未満の差)
をよく見ると、
DP[i+1][k+1][h] = min(DP[i][k][h-1] + hとh-1の差, min(DP[i][k][h-1未満] + hとh-1未満の差))
DP[i+1][k+1][h] = min(DP[i][k][h-1] + hとh-1の差, min(DP[i][k][h-1未満] + h-1とh-1未満の差) + hとh-1の差)
DP[i+1][k+1][h] = min(DP[i][k][h-1] + hとh-1の差, DP[i+1][k+1][h-1] + hとh-1の差)
という感じである。
あとは、これをまとめればいいが、h<h2は以前の結果を使用するので、これを最初にやって、残りをやっていく。

int N, K, H[301];
ll dp[301][301][301];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> H[i];

    auto dic = compress1(H, N, { 0 });
    int M = dic.size();

    rep(i, 0, N + 1) rep(k, 0, K + 1) rep(h, 0, M) dp[i][k][h] = infl;
    dp[0][0][0] = 0;

    rep(i, 0, N) {
        rep(k, 0, K) rep(h, 1, M) chmin(dp[i + 1][k + 1][h], min(dp[i][k][h - 1], dp[i + 1][k + 1][h - 1]) + dic[h] - dic[h - 1]);
        rep(k, 0, K) {
            ll mi = infl;
            rrep(h, M - 1, 0) {
                chmin(mi, dp[i][k][h]);
                chmin(dp[i + 1][k + 1][h], mi);
            }
        }
        rep(k, 0, K + 1) rep(h, 0, M) chmin(dp[i + 1][k][H[i]], dp[i][k][h] + max(0, dic[H[i]] - dic[h]));
    }

    ll ans = infl;
    rep(k, 0, K + 1) rep(h, 0, M) chmin(ans, dp[N][k][h]);
    cout << ans << endl;
}