题解 P2467 【[SDOI2010]地精部落】

xzyxzy · 2018-11-04 16:45:40 · 题解

可以算是优质题解？虽然我也是看了题解才完成的本题

只用一维DP，没有那么复杂

• 首先发现一个性质：/\/\....和\/\/的数量一样多
• 设f[i]表示1到i的排列中，首个下降的波动序列个数
• 转移：加入i，一定是放在山峰的位置，枚举在第j个位置，则f[i]+=f[j-1]*f[i-j]*C[i-1][j-1]
• 意思是在剩余的i-1个数中选j-1个放在左边，然后左右的数字分别离散话之后的方案就是f[j-1]、f[i-j]

代码很简单

#include<iostream>
using namespace std;
const int N=4210;
int C[2][N],f[N],P,n;
int main()
{
    cin>>n>>P;C[0][0]=C[1][0]=f[0]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
        {
            if(j&1) (f[i]+=1ll*f[j-1]*f[i-j]%P*C[(i-1)&1][j-1]%P)%=P;
            C[i&1][j]=(C[(i-1)&1][j]+C[(i-1)&1][j-1])%P;
        }
    cout<<2ll*f[n]%P<<endl;
}
Blog:https://www.cnblogs.com/xzyxzy

C要滚动因为要卡空间（BZOJ）