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;
}