C++14(g++5.4) 解法, 执行用时: 5ms, 内存消耗: 508K, 提交时间: 2020-01-15 16:28:13

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e3+10;
int n,a[N];
inline int solve(int l,int r){
	int mi=1e14,pre=l,res;
	for(int i=l;i<=r;i++)	mi=min(mi,a[i]);	res=mi;
	for(int i=l;i<=r;i++){
		a[i]-=mi;
		if(!a[i])	res+=solve(pre,i-1),pre=i+1;
	}
	if(pre!=r+1)	res+=solve(pre,r);
	return min(res,r-l+1);
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++)	cin>>a[i];
	cout<<solve(1,n);
	return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 4ms, 内存消耗: 412K, 提交时间: 2023-07-03 16:38:16

#include<iostream>
using namespace std;
const int N=3e3+10;
int n;
int a[N];
int dfs(int l,int r)
{
    int ans=0,minn=2e9,pre=l;
    for(int i=l;i<=r;i++) minn=min(minn,a[i]);
    ans+=minn;
    for(int i=l;i<=r;i++){
        a[i]-=minn;
        if(a[i]==0){
            ans+=dfs(pre,i-1);
            pre=i+1;
        }
    }
    if(pre!=r+1) ans+=dfs(pre,r);
    return min(ans,r-l+1);
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    cout<<dfs(1,n);
}

C++(clang++ 11.0.1) 解法, 执行用时: 3ms, 内存消耗: 444K, 提交时间: 2022-10-06 21:50:26

#include<bits/stdc++.h>
using namespace std;
const int N=3010;
int a[N],n;
int dfs(int l,int r)
{
    int mi=1e9;
    for(int i=l;i<=r;i++)mi=min(mi,a[i]);
    int res=mi,pre=l;
    for(int i=l;i<=r;i++)
    {
        a[i]-=mi;
        if(!a[i])res+=dfs(pre,i-1),pre=i+1;
    }
    if(pre!=r+1)res+=dfs(pre,r);
    return min(res,r-l+1);
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    cout<<dfs(1,n);
}