首页 > 代码库 > BZOJ 1801 中国象棋（DP）

BZOJ 1801 中国象棋（DP）

2024-07-09 00:11:09   219人阅读

题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=1801

题意：在n*m的棋盘上放若干炮使得不互相攻击。有多少种放法？可以放0个、1个。。。。只要不互相攻击就行。。

思路：f[i][j][k]前i行j列有1个炮、k列有两个炮。

 

int n,m;i64 f[N][N][N];void up(i64 &x,i64 y){    x+=y;    x%=mod;}i64 C(int x){    return x*(x-1)/2;}int main(){    RD(n,m);    f[1][0][0]=1;    f[1][1][0]=m;    f[1][2][0]=m*(m-1)/2;    int i,j,k;    for(i=2;i<=n;i++)    {        for(j=0;j<=m;j++) for(k=0;k<=m;k++)        {            if(j+k>m) continue;            f[i][j][k]=f[i-1][j][k];                        if(j>0) up(f[i][j][k],f[i-1][j-1][k]*(m-j-k+1));            if(k>0) up(f[i][j][k],f[i-1][j+1][k-1]*(j+1));                        if(j>=2) up(f[i][j][k],f[i-1][j-2][k]*C(m-j-k+2));            if(k>=1) up(f[i][j][k],f[i-1][j][k-1]*(m-j-k+1)*j);            if(k>=2) up(f[i][j][k],f[i-1][j+2][k-2]*C(j+2));        }    }    i64 ans=0;    for(j=0;j<=m;j++) for(k=0;k<=m;k++)    {        up(ans,f[n][j][k]);    }    PR(ans);}

 

 

 


联系
我们