【題解】Codeforces 1400E. Clear the Multiset

#include <iostream>
using namespace std;
 
int n, a[5005], ans;
 
int f(int l, int r, int h){
    int mn = a[l];
    for (int i = l+1; i <= r; i++){
        mn = min(mn, a[i]);
    }
    int pre = 0;
    int x = mn-h;
    for (int i = l; i <= r; i++){
        if (a[i] == mn && pre){
            x += f(pre, i-1, mn);
            pre = 0;
        }
        else if (a[i] != mn && !pre) pre = i;
    }
    if (pre) x += f(pre, r, mn);
    x = min(x, r-l+1);
    return x;
}
 
int main() {
    cin >> n;
    int pre = 0;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        if (!a[i] && pre){
            ans += f(pre, i-1, 0);
            pre = 0;
        }
        else if (a[i] && !pre) pre = i;
    }
    if (a[pre]) ans += f(pre, n, 0);
    cout << ans << "\n";
}