题解 | #楼房拆除#

using namespace std;
vector<long long> h;

int solve(int l, int r) {
    if (l == r) {
        if (h[l] == 0) return 0;
        return 1;
    }
    if(l > r) return 0;
    long long mn = 1e9 + 1;
    for (int i = l; i <= r; i++) mn = min(mn, h[i]);
    for (int i = l; i <= r; i++) h[i] -= mn;
    int ret(1);
    vector<int> interval;
    for (int i = l; i <= r; i++) if (h[i] == 0) interval.push_back(i);
    interval.push_back(l - 1); // [l,r] 
    interval.push_back(r + 1);

    sort(interval.begin(), interval.end());

    for (int i = 1; i < interval.size(); i++) {
        ret += solve(interval[i - 1] + 1, interval[i] - 1); // 包含[l,r] 
    }
    return ret;
}


int main() {
    int n;
    cin >> n;
    h.resize(n+1);

    for (int i = 1; i <= n; i++) cin >> h[i];

    cout << solve(1, n) << endl;
    return 0;
}