Grand Garden [AtCoder Beginner Contest 116 C]

https://atcoder.jp/contests/abc116/tasks/abc116_c

解説

https://atcoder.jp/contests/abc116/submissions/4059474

なるべく大きい区間から順にやっていけばいい。
操作を逆に考えて、大きい区間から減らしていく。
高さがあるもので隣り合っているものを連結しながら考えていく。
何をすべきかは結構分かるかと思うが、実装に落とすのが難しい。
連結する所は区間になるので、区間で考えればいい。
これは再帰関数でやる。
f(L, R) := 区間[L,R)を全て0にするために必要な回数を計算する
区間を分割するときは、0である添字をメモしておき、それを使って、0でない区間を再帰していく。

int N, H[101];
//---------------------------------------------------------------------------------------------------
int ans = 0;
void f(int L, int R) {
    if (L >= R) return;

    int mi = inf;
    rep(i, L, R) chmin(mi, H[i]);

    ans += mi;
    rep(i, L, R) H[i] -= mi;

    vector<int> zero;
    zero.push_back(-1);
    rep(i, L, R) if(H[i] == 0) zero.push_back(i);
    zero.push_back(R);

    int n = zero.size();
    rep(i, 0, n - 1) f(zero[i] + 1, zero[i + 1]);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> H[i];

    f(0, N);
    cout << ans << endl;
}