有关时间复杂度

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5000+5;
int n,ans;
int a[N];
int sta[N],stalen;
int son[N][2];
int dfs(int x,int l,int r,int del){
	if(l>r){
		return 0;
	}
	if(l==r){
		if(del!=a[x]){
			return 1;
		}
		return 0;
	}
	int sum=a[x]-del,sum1=1;
	if(son[x][0]){
		sum+=dfs(son[x][0],l,x-1,a[x]);
		sum1+=dfs(son[x][0],l,x-1,del);
	}
	if(son[x][1]){
		sum+=dfs(son[x][1],x+1,r,a[x]);
		sum1+=dfs(son[x][1],x+1,r,del);
	}
//	printf("{%d %d %d %d}\n",x,l,r,del);
//	printf("[[%d %d]]\n",sum,sum1);
//	return min(sum,r-l+1);
	return min(sum,sum1);
}
signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	for(int i=1;i<=n;i++){
		while(stalen>=1&&a[sta[stalen]]>a[i]){
			stalen--;
		}
		son[i][0]=son[sta[stalen]][1];
		son[sta[stalen]][1]=i;
		sta[++stalen]=i;
	}
//	for(int i=1;i<=n;i++){
//		printf("[%d %d]\n",son[i][0],son[i][1]);
//	}
	printf("%lld",dfs(sta[1],1,n,0));
	return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5000+5;
int n,ans;
int a[N];
int sta[N],stalen;
int son[N][2];
int dfs(int x,int l,int r,int del){
	if(l>r){
		return 0;
	}
	if(l==r){
		if(del!=a[x]){
			return 1;
		}
		return 0;
	}
	int sum=a[x]-del,sum1=1;
	if(son[x][0]){
		sum+=dfs(son[x][0],l,x-1,a[x]);
//		sum1+=dfs(son[x][0],l,x-1,del);
	}
	if(son[x][1]){
		sum+=dfs(son[x][1],x+1,r,a[x]);
//		sum1+=dfs(son[x][1],x+1,r,del);
	}
//	printf("{%d %d %d %d}\n",x,l,r,del);
//	printf("[[%d %d]]\n",sum,sum1);
	return min(sum,r-l+1);
//	return min(sum,sum1);
}
//上面是两串代码的唯一区别
signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	for(int i=1;i<=n;i++){
		while(stalen>=1&&a[sta[stalen]]>a[i]){
			stalen--;
		}
		son[i][0]=son[sta[stalen]][1];
		son[sta[stalen]][1]=i;
		sta[++stalen]=i;
	}
//	for(int i=1;i<=n;i++){
//		printf("[%d %d]\n",son[i][0],son[i][1]);
//	}
	printf("%lld",dfs(sta[1],1,n,0));
	return 0;
}