首页 > 代码库 > BZOJ 1801中国象棋 DP
BZOJ 1801中国象棋 DP
将题目化简为设计01矩阵 每一行每一列至多2个1。求有几种方案。
设f[i][j][k]代表到第i行有j列放了1个象棋k列放了0个象棋有两个象棋的列不用考虑因为不能再放了。
递推方程如下：
f[i][j][k]=f[i-1][j][k] 第i行不放。
f[i][j][k]+=f[i-1][j-1][k+1]*(k+1) 在i-1行中任选一列（该列的棋子数=0）后面放一颗。有 k+1种放法。
f[i][j][k]+=f[i-1][j+1][k]*(j+1) 选一列（该列棋子数=1）
f[i][j][k]+=f[i-1][j][k+1]*j*(k+1) 选两列 一列棋子数=1 一列棋子数=0
f[i][j][k]+=f[i-1][j-2][k+2]*(k+2)*(k+1)/2 选两列棋子数=0的
f[i][j][k]+=f[i-1][j+2][k]*(j+2)*(j+1)/2 选两列棋子数=1的
最后统计 f[n][i][j] 0<=i,j<=m;
代码如下：
1 #include<cstdio> 2 #include<iostream> 3 #define MOD 9999973 4 #define MAXN 105 5 #define For(i,x,y) for(int i=x;i<=y;++i) 6 using namespace std; 7 long long f[MAXN][MAXN][MAXN]; 8 int main() 9 {10 int n,m;cin>>n>>m;11 f[1][0][m]=1;12 f[1][1][m-1]=m;13 f[1][2][m-2]=m*(m-1)/2;14 For(i,2,n)15 {16 For(j,0,m)17 {18 For(k,0,m)19 {20 f[i][j][k]=(f[i-1][j][k]+f[i-1][j-1][k+1]*(k+1)%MOD+f[i-1][j+1][k]*(j+1)%MOD)%MOD+f[i-1][j][k+1]*j*(k+1)%MOD;21 f[i][j][k]+=(f[i-1][j-2][k+2]*(k+2)*(k+1)/2)%MOD+f[i-1][j+2][k]*(j+2)*(j+1)/2;22 f[i][j][k]%=MOD;23 }24 }25 }26 long long ans=0;27 For(i,0,m)28 {29 For(j,0,m)30 {31 ans+=f[n][i][j];32 ans%=MOD;33 }34 }35 printf("%lld",ans);36 }
BZOJ 1801中国象棋 DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。