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\) 个被砍的排列数。
- \(a(i)=a(i+1)\)：\(f(i,j)=\sum_{k=1}^{i}f(i-1,k)\)；
- \(a(i)<a(i+1)\)：\(f(i,j)=\sum_{k=j}^{i}f(i-1,k)\)；
- \(a(i)>a(i+1)\)：\(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;
}
``