记忆化搜索

第一时间没有想到好的思路，就走上了搜索的不归路。
如果有想写这种思路的可以做参考。OrzOrzOrzOrzOrz

时间复杂度

$O(n)$

C++ 代码

#include <stdio.h>
#include <algorithm>

using namespace std;

const int N = 100005;

int n;
int h[N];

int dfs(int L,int R,int H) //保证传入的区间中，没有小于H的数，H可以理解为当前建造的高度。
{
    if(L >= R) return h[L] - H;
    int _min = 9999999, res = 0;
    for (int i = L; i <= R; ++ i) _min = min(_min, h[i]);

    int new_L = L;
    for (int i = L; i <= R; ++ i)
    {
        if(h[i] == _min)
        {
            res += dfs(new_L, i - 1, _min);
            new_L = i + 1;
        }
    }
    if(h[R] > _min) res += dfs(new_L, R, _min);
    res += _min - H;
    return res;
}


int main(void)
{
    int res = 0;
    scanf("%d",&n);
    int L = 0;
    for (int i = 0; i < n; ++ i)
    {
        scanf("%d", h + i);
        if(!h[i])
        {
            res += dfs(L, i - 1, 0);
            L = i + 1;
        }
    }
    if(h[n - 1]) res += dfs(L, n - 1, 0);
    printf("%d",res);
    return 0;
}