Description
Link.
有 $n$ 棵树，每棵的高度为 $a(i)$，看到一棵树对答案的贡献为 $a(i-1)+a(i)+a(i+1)$（未定义范围为 $0$），求使得答案最小的砍树顺序的数量。
Solution
口胡瑇师。不过这个 F 比上次的 Lagrange 插值阳间多了。
考虑每一个元素的贡献次数。发现这个次数的区间是 $[1,3]$，对应树 $i$ 在树 $i-1/i+1$ 之前 / 之后砍倒的情况。
那么我们直接贪心，使得答案最小的砍树顺序一定是：
- $a(i)<a(i+1)$ 先砍 $i+1$，再砍 $i$；
- otherwise：先砍 $i$，再砍 $i+1$。
然后就可以 DP 仂。设 $f(i,j)$ 为树 $i$ 在是第 $j$ 个被砍的排列数，注意这里的 $j$ 是相对的。
- $a(i-1)=a(i)$：$f(i,j)=\sum_{k=1}^{i}f(i-1,k)$；
- $a(i-1)<a(i)$：$f(i,j)=\sum_{k=j}^{i}f(i-1,k)$；
- $a(i-1)>a(i)$：$f(i,j)=\sum_{k=1}^{j}f(i-1,k)$。
使用前缀和优化。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {
ll x=0,f=0;
char ch=getchar();
while(ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+(ch&15),ch=getchar();
return f?-x:x;
}
const int N=4100,MOD=1e9+7;
ll dp[N][N],sum[N],a[N];
signed main() {
int n=read();
for(int i=1; i<=n; ++i) a[i]=read();
dp[1][1]=1;
for(int i=2; i<=n; ++i) {
for(int j=1; j<i; ++j) (sum[j]=sum[j-1]+dp[i-1][j])%=MOD;
for(int j=1; j<=i; ++j)
if(a[i]==a[i-1]) dp[i][j]=sum[i-1];
else if(a[i]>a[i-1]) dp[i][j]=(sum[i-1]-sum[j-1]+MOD)%MOD;
else dp[i][j]=sum[j-1];
}
ll ans=0;
for(int i=1; i<=n; ++i) (ans+=dp[n][i])%=MOD;
printf("%lld\n",ans);
return 0;
}