思维难度很大的DP
设 f [ i ] 表示长度为 i 的山脉的合法方案数
考虑枚举最高的山的位置 j
那么在不考虑 j 左右两边是山谷或山脉的情况下
f[ i ] += f[ j-1 ] * f[ i-j ] * C[ i-1 ] [ j-1 ]（C[ i-1 ] [ j-1 ] 表示i-1种高度选出 j-1 种高度的山给左边一段，i-1是因为最高峰不能取）
就是山峰左边一段的方案乘上右边一段的方案再乘上 组合数
乘上C是因为 f[ j-1 ] 只有山高度为 1~j-1 的情况
在有 i 个山 的情况下 f[ j-1 ] 指的就变成了相对的高度的方案数
山的高度的取法就有 C[i-1] [ j-1 ] 种
然后考虑 j 的左右两边的山的情况
设 f [ i ] [ 0/1 ] i 的含义不变， 0表示第一位为山谷，1表示第一位为山峰
可以发现，如果我们知道山脉的长度以及第一位的状态，我们就可以得到最后一位的状态：
如果长度为奇数，最后一个山的状态就与第一位相反
反之长度为偶数，最后一个山的状态就与第一位相同
因为我们枚举的是最高峰的位置
所以左边半段的山脉的最后一个山必须为山谷
右边半段的山脉的第一个山必须为山谷
所以可以得出转移方程：
if(j&1) f[ i ] [ 0 ] += f[ j-1 ] [ 0 ] * f[ i-j ] [ 0 ] * C[ i-1 ] [ j-1 ]
else f[ i ] [ 1 ] += f[ j-1 ] [ 1 ] * f[ i-j ] [ 0 ] * C[ i-1 ] [ j-1 ]
（左边半段的第一位一定要与总状态的第一位相同）
有了方程就好搞了
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; long long n,m; long long f[4207][2],C[4207][4207]; int main() { scanf("%lld%lld",&n,&m); //先预处理一波组合数 C[0][0]=1; for(int i=1;i<=n;i++) { C[i][0]=C[i][i]=1; for(int j=1;j<i;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%m; } f[0][0]=f[0][1]=f[1][0]=f[1][1]=1;//初始状态 for(int i=2;i<=n;i++) for(int j=1;j<=i;j++)//注意j的范围 { if(j&1) f[i][0]=(f[i][0]+( ( f[j-1][0]*f[i-j][0]%m ) * C[i-1][j-1]%m) )%m; else f[i][1]=(f[i][1]+( ( f[j-1][1]*f[i-j][0]%m ) * C[i-1][j-1]%m) )%m; } printf("%lld",(f[n][0]+f[n][1])%m); return 0; }