积木大赛

解题思路

搭建一座宽度为 n 的大厦，大厦可以看成由 n 块宽度为1的积木组成，第 i 块积木的最终高度需要是 h[i] 。
在搭建开始之前，没有任何积木（可以看成 n 块高度为 0 的积木）。接下来每次操作，可以选择一段连续区间 [L, R] ，然后将第 L 块到第 R 块之间（含第 L 块和第 R 块）所有积木的高度分别增加 1 。
求建造大厦的最少的操作次数。

递归：
每次都选择最大限度的连续区间 [left, right]，其最小的高度为 mi，其所在的下标记录在 vmin。
这时，操作 mi 次，计入 cnt，vmin 中的下标位置已经达到所需高度。
将区间从 [left, right] 以 vmin 中的下标为分界线，又分成若干个连续区间，直至区间不能分割为止。

C++代码

#include<cstdio>
#include<vector>
using namespace std;

int opCnt(vector<int>& h, int left, int right){
    if(left > right)
        return 0;
    if(left == right)
        return h[left];
    vector<int> vmin;
    vmin.push_back(left);
    int mi = h[left];
    for(int i=left+1; i<=right; ++i){
        if(h[i] < mi){
            vmin.clear();
            vmin.push_back(i);
            mi = h[i];
        }
        else if(h[i] == mi)
            vmin.push_back(i);
    }
    int cnt = mi;
    for(int i=left; i<=right; ++i)
        h[i] -= mi;
    cnt += opCnt(h, left, vmin[0]-1);
    for(int i=1; i<vmin.size(); ++i){
        cnt += opCnt(h, vmin[i-1]+1, vmin[i]-1);
    }
    cnt += opCnt(h, vmin.back()+1, right);
    return cnt;
}

int main(){
    int n;
    scanf("%d", &n);
    vector<int> h(n);
    for(int i=0; i<n; ++i)
        scanf("%d", &h[i]);
    int cnt = opCnt(h, 0, n-1);
    printf("%d", cnt);
    return 0;
}

C++代码（贪心，差分）

#include<cstdio>
#include<vector>
using namespace std;

int main(){
    int n;
    scanf("%d", &n);
    vector<int> h(n);
    for(int i=0; i<n; ++i)
        scanf("%d", &h[i]);
    int cnt = h[0];
    for(int i=1; i<n; ++i){
        if(h[i] > h[i-1])
            cnt += h[i]-h[i-1];
    }
    printf("%d", cnt);
    return 0;
}