§ 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;
}