P2467 [SDOI2010] 地精部落

2018-05-15 14:41:57


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;
}