RT

有一篇题解就是这么写的

我交了一遍

也是MLE

求正解(或者这个方法可以优化?)

#include<bits/stdc++.h>
using namespace std;

int n,a[5010];
int lw[5010][5010];
int id[5010][5010];

int dfs(int l,int r,int h) {
    if(l>r) return 0;
    if(l==r) {
        if(h==a[l]) return 0;
        else return 1;
    }
    int res1=r-l+1;
    int res2=lw[l][r]-h;
    res2+=dfs(l,id[l][r]-1,lw[l][r])+dfs(id[l][r]+1,r,lw[l][r]);
    return min(res1,res2);
}

int main() {
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) {
        lw[i][i]=a[i];
        id[i][i]=i;
        for(int j=i+1;j<=n;j++) {
            if(lw[i][j-1]>=a[j]) {
                lw[i][j]=a[j];
                id[i][j]=j;
            } else {
                lw[i][j]=lw[i][j-1];
                id[i][j]=id[i][j-1];
            }
        }
    }
//    for(int i=1;i<=n;i++) {
//    	for(int j=1;j<=n;j++) {
//    		cout<<id[i][j]<<" ";
//		}
//		cout<<endl;
//	}
    cout<<dfs(1,n,0);
}