其实这题很简单，只是dp难想
$f_{i,j}$ 前i座山脉，第i座山脉是第j小，且i-1座山脉比第i座高，即第i座山脉是山谷
$g_{i,j}$ 第i座是山峰
值得注意的是，j表明第j小，也就是说前i座山脉不一定只有[1,i]的山脉
dp方程：
$$ f_{i,j}=\sum_{k=j}^{i-1}g_{i-1,k} $$
解释一下为什么是k从j开始
因为当前第i座是山谷，加入之后，之前的第j小就变成了第j+1小
再想一下，如果原来的一个排列每座山脉都翻一下，即每座山$h_i=i-h_i+1$
山谷与山峰互换，那么得到的方案一定是与原来 一 一 对应
所以 $f_{i,j}=g_{i,i-j+1}$
那么原来的dp方程变成
$$ f_{i,j}=\sum_{k=1}^{i-j}f_{i-1,k} $$
#include <cstdlib> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define ll long long #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; int n,mod; ll f[2][4206]; ll dp() { if(n==1) return 1; int now=0,pre; ll tt; f[0][1]=1; for(int i=2;i<=n;++i) { now^=1;pre=now^1; tt=0; for(int j=i-1;j>=1;--j) { tt=(tt+f[pre][(i-1)-j+1])%mod; f[now][j]=tt; } } ll ans=0; for(int i=1;i<=n;++i) ans=(ans+f[now][i])%mod; return ans*2%mod; } int main(){ scanf("%d%d",&n,&mod); printf("%lld",dp()); }
原文：http://www.cnblogs.com/A-LEAF/p/7679756.html
