BZOJ1801: [Ahoi2009]chess 中国象棋【DP】

1801: [Ahoi2009]chess 中国象棋

【题目描述】

传送门

【题解】

题解

代码如下

#include<cstdio>
#include<algorithm>
using namespace std;
const int MOD=9999973;
typedef long long LL;
int n,m;LL f[105][105][105],Ans;
int main(){
    scanf("%d%d",&n,&m);if(n>m) swap(n,m);f[0][0][0]=1;
    for(int i=1;i<=n;i++)
    for(int j=0;j<=m;j++)
    for(int k=0;k+j<=m;k++){
        f[i][j][k]=f[i-1][j][k];//不放 
        if(j  ) f[i][j][k]=(f[i][j][k]+f[i-1][j-1][k]*(m-(j-1)-k)%MOD)%MOD;//在没炮的地方放一个
        if(k  ) f[i][j][k]=(f[i][j][k]+f[i-1][j+1][k-1]*(j+1)%MOD)%MOD;//在有一个炮的地方放一个 
        if(j>1) f[i][j][k]=(f[i][j][k]+f[i-1][j-2][k]*(m-(j-2)-k)*(m-(j-2)-k-1)/2%MOD)%MOD;//在没炮的地方放两个 
        if(k  ) f[i][j][k]=(f[i][j][k]+f[i-1][j][k-1]*(m-j-(k-1))*j%MOD)%MOD;//一个放在有炮的地方,一个放在没炮的地方。
        if(k>1) f[i][j][k]=(f[i][j][k]+f[i-1][j+2][k-2]*(j+2)*(j+2-1)/2%MOD)%MOD;//放在有炮的地方 
    }
    for(int i=0;i<=m;i++)
    for(int j=0;j+i<=m;j++) Ans=(Ans+f[n][i][j])%MOD;
    printf("%d\n",Ans);
    return 0;
}

发表评论

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部