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

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)