P2467 [SDOI2010] 地精部落

dp求方案数的问题 用f[i]表示长度为i的第一位为山峰的波动山脉数量 显然第一位是山谷和山峰的数量是一样的 所以最终答案为f[n]*2 可以以最大数的位置为分界点，把长度为n的序列分成两份 当最大数在奇数位时，第一个一定是山峰 当最大数在偶数位时，第一个一定是山谷 所以通过枚举最大数的位置进行状态转移 把两段的方案数相乘再乘以组合数，求出总和即为f[i] ~~好像可以用滚动数组优化然而我不会~~ ``` #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const int N=4205; int n,p,f[N],c[N][N]; inline void calc() { c[0][0]=1; for (int i=1;i<=n;i++) { c[i][0]=1; for (int j=1;j<=i;j++) c[i][j]=(c[i-1][j]+c[i-1][j-1])%p; } } int main() { scanf("%d%d",&n,&p); f[0]=f[1]=1; calc(); for (int i=2;i<=n;i++) for (int j=1;j<i;j+=2)//枚举最大数位置 f[i]=(f[i]+(ll)f[j]*c[i-1][j]%p*f[i-j-1])%p; printf("%d\n",f[n]*2%p); return 0; } ```