首先我们可以思考\(a_i\)和\(a_{i+1}\)先砍哪棵花费少。
可以看出，当\(a[i]<a[i+1]\)时，先砍\(a[i+1]\)，反之亦然。
所以这个题转化成了：给定\(n-1\)个关系，分别表示\(n\)个值中相邻两个的大小关系，问满足这些关系的序列个数。与Atcoder Educational DP Contest T很像，但是这里不是求排列，因为可以有相等的元素，所以两两元素之间的关系有三种>,<,=。前两种的状态转移方程见上面的链接，至于遇到=，就直接等于前\(i-1\)个元素的答案。
具体见代码。
点击查看代码
#include<bits/stdc++.h>
#define mod 1000000007
#define int long long
using namespace std;
int n,f[4010][4010],sum[4010][4010];
int a[4010];
int s[4010];
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
if(a[i]>a[i-1]) s[i]=1;
else if(a[i]<a[i-1]) s[i]=-1;
else s[i]=0;
}
sum[1][1]=1;
for(int i=2;i<=n;i++){
for(int j=1;j<=i;j++){
if(s[i]==1){
f[i][j]=(sum[i-1][j-1])%mod;
}else if(s[i]==-1){
f[i][j]=(sum[i-1][i-1]-sum[i-1][j-1]+mod)%mod;
}else{
f[i][j]=sum[i-1][i-1];
}
sum[i][j]=(sum[i][j-1]+f[i][j])%mod;
}
}
cout<<sum[n][n];
return 0;
}