#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int a[100005]={};
int ans=0;
int at=0;
void build(int l,int r){
	int mn=0x3f3f3f3f;
	for(int i=l;i<=r;i++) if(a[i]<mn){
		mn=a[i];
		at=i;
		//更新最小值和零点 
	}
	for(int i=l;i<=r;i++) a[i]-=mn;
	//建造 
	ans+=mn;
	//ans更新 
	return;
}
void dfs(int l,int r){
	if(l>r) return;
	//如果为负区间就退出 
	build(l,r);
	//操作函数 
	dfs(l,at-1);
	dfs(at+1,r);
	//从零点左右再递归 
}
signed main(){
	cin>>n;
	for(int i=0;i<n;i++) cin>>a[i];
	dfs(0,n-1);
	//开始递归 
	cout<<ans<<"\n";
	return 0;
}

与P5019 [NOIP2018 提高组] 铺设道路 基本一致

我用的是dfs，贪心更快