题面：
分析：
首先，强烈谴责将此题放到数学中
主流算法貌似是一个什么波动序列（本人不会）
拿过题面看到数据范围首先想到状压（20%），后来在whs大神的启发下，发现用状压保存山脉的状态没什么卵用。这里有个比较重要的性质：及维护一个固定长度的山脉，只要保证山峰高度不同，那么方案数是固定的，与山峰具体高度无关（有点像Perm排列计数）。所以只要枚举山脉长度，将新山峰插入转移即可。
dp[k][len][i]为考虑到的山脉长度为len,山脉末尾山峰的相对高度排名为i，是山峰还是谷地的方案数。
dp[k][len][i]=∑dp[k^1][len-1][s]
敲小黑板：
如果为山峰，s属于（1，i-1），因为在原山脉排名为s，在新山脉排名也为s
为谷地时，s属于（i，len-1），在新山脉中所要的其实是（i+1，len），但除去了i，在原山脉实际为（i，len-1）
1 #include<iostream> 2 #include<cstdio> 3 #define MAXN 4210 4 using namespace std; 5 int N; 6 int P; 7 int dp[2][MAXN][MAXN]; 8 int res; 9 int main(){ 10 scanf("%d%d",&N,&P); 11 dp[0][1][1]=dp[1][1][1]=1; 12 for(int len=2;len<=N;++len) 13 for(int i=1;i<=len;++i){ 14 for(int s=i;s<len;++s) 15 dp[0][len][i]=(dp[0][len][i]+dp[1][len-1][s])%P; 16 for(int s=i-1;s>=1;--s) 17 dp[1][len][i]=(dp[1][len][i]+dp[0][len-1][s])%P; 18 } 19 for(int i=1;i<=N;++i) 20 res=(res+dp[0][N][i]+dp[1][N][i])%P; 21 printf("%d\n",res%P); 22 }
对，还是WA了，能看到4200×4200，时间长空间大，考虑滚动数组和前缀和即可
最后
#include<iostream> #include<cstdio> #define MAXN 4210 using namespace std; int N; int P; int dp[2][2][MAXN]; int res; int qsum[2][2][MAXN]; int main(){ scanf("%d%d",&N,&P); int now=0,past=1; dp[past][0][1]=dp[past][1][1]=1; qsum[past][0][1]=qsum[past][1][1]=1; for(int len=2;len<=N;++len){ for(int i=1;i<=len;++i){ dp[now][0][i]=qsum[past][1][i]; // printf("%d 0 %d %d\n",len,i,dp[now][0][i]); qsum[now][0][i]=(qsum[now][0][i-1]+dp[now][0][i])%P; } for(int i=len;i>=1;--i){ dp[now][1][i]=qsum[past][0][i-1]; // printf("%d 1 %d %d\n",len,i,dp[now][1][i]); qsum[now][1][i]=(qsum[now][1][i+1]+dp[now][1][i])%P; } now=past;past^=1; } printf("%d\n",(qsum[past][0][N-1]+qsum[past][1][2])%P); }
原文：https://www.cnblogs.com/2018hzoicyf/p/11137164.html
