AtCoder Beginner Contest 145：F - Laminate

問題

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

解法

まず，数列 H を扱いやすいように座標圧縮しておく（最小を 1 としなければいけないことに注意）．そうすることで H の要素は高々 N + 1 以下になる．また，H[k] < H[k + 1] となるときのみ，新たに H[k + 1] - H[k] 回の操作が必要となる（反対に，高さが同じか低くなるときには，新たに操作は必要にならない）．これを踏まえ，以下の DP を考える．

dp(i, j, k) := i - 1 列目までのいくつかで操作を行い，あと j 回操作が可能で，i - 1 列目の H が k であるときの，これから行わなければならない操作の回数の最小値

遷移は H[k] を k に変更するか，そのまま変更しないかの 2 通りであるから，

dp(i, j, k) = min(dp(i + 1, j, H[i]) + max(H[i] - k, 0), dp(i + 1, j - 1, k))

となる．max(H[i] - k, 0) は H[i] <= k のときは操作回数は増えないことを意味している．この部分で座標圧縮した分の差を復元する必要がある（操作回数が小さくなってしまうので）．O(N^2 * K)．

解答

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