Codeforces Round #500 (Div. 1) [based on EJOI]: C. Hills
problem
長さ $n$ の整数列 $a$ が与えられる。 費用 $1$ 払って好きな要素を $a_i$ を $1$ 小さくする操作を好きな回数行なえる。 $a _ {i - 1} \lt a_i \land a_i \gt a _ {i + 1}$ を満たすような $i$ を $k$ 個以上作るのに必要な費用の最小値はいくらか、すべての $k$ について答えよ。
solution
DP。$i$項まで見て$k$個の頂点を作り直近の$2$要素が$j \in \{ (a _ {i - 2} \text{を頂点にした}), (a _ {i - 1} \text{を頂点にした}), (\text{どちらも頂点でない}) \}$であるような状態を作るための費用を$\mathrm{dp}(i, j, k)$とする。$O(NK)$。
implementation
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define ALL(x) begin(x), end(x)
using namespace std;
template <class T> inline void chmin(T & a, T const & b) { a = min(a, b); }
constexpr int INF = 1e9 + 7;
int main() {
// input
int n; cin >> n;
vector<int> a(n); REP (i, n) cin >> a[i];
// solve
auto delta = [](int house, int neighbouring) { return max(0, neighbouring - house + 1); };
int k_max = (n + 1) / 2;
vector<array<int, 3> > cur, prv;
cur.assign(k_max + 1, (array<int, 3>) { INF, INF, INF });
cur[0][0] = 0;
REP (i, n) {
cur.swap(prv);
cur.assign(k_max + 1, (array<int, 3>) { INF, INF, INF });
cur[0][0] = 0;
REP (k, k_max) {
chmin(cur[k + 1][0], prv[k + 1][0]);
chmin(cur[k + 1][0], prv[k + 1][2]);
if (i == 0) chmin(cur[k + 1][1], prv[k ][0]);
if (i >= 1) chmin(cur[k + 1][1], prv[k ][0] + delta(a[i], a[i - 1]));
if (i >= 2) chmin(cur[k + 1][1], prv[k ][2] + delta(a[i], min(a[i - 1], a[i - 2] - 1)));
if (i >= 1) chmin(cur[k + 1][2], prv[k + 1][1] + delta(a[i - 1], a[i]));
}
}
// output
REP3 (k, 1, k_max + 1) {
cout << *min_element(ALL(cur[k])) << " ";
}
cout << endl;
return 0;
}