博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
bzoj1801: [Ahoi2009]chess 中国象棋
阅读量:5217 次
发布时间:2019-06-14

本文共 1145 字,大约阅读时间需要 3 分钟。

看到这种题,要么猥琐数学题,要么DP,还能搞搞什么矩乘什么的。

然后这题就是硬刚DP。很容易看出每行每列的棋子数都不超过2吧

f[i][j][k]表示枚举到第i行,有j列有1个棋子,有k列有2个棋子。然后m-j-k就可以的到没放的多少列吧。

枚举每一行,分六种情况。

1、这一行不放

2、放一个,放在没有棋子的列里

3、放一个,放在有棋子的列里

4、放两个,都放在没有棋子的列里

5、放两个,一个放在没有棋子的列里,一个放在有棋子的列里

6、放两个,都放在有棋子的列里

然后转移。方程不写了(其实代码你也看得到),推的要死要活的,丑。

 

无脑long long谢谢。

#include
#include
#include
#include
#include
#include
using namespace std;typedef long long LL;const LL mod=9999973;LL f[110][110][110];int main(){ LL n,m; scanf("%lld%lld",&n,&m); if(n==1){printf("%lld\n",1+m+m*(m-1)/2);return 0;} memset(f,0,sizeof(f)); f[1][0][0]=1; f[1][1][0]=m; f[1][2][0]=m*(m-1)/2; //init LL ans=0; for(int i=2;i<=n;i++) for(int j=0;j<=m;j++) for(int k=0;k+j<=m;k++) { f[i][j][k]=(f[i][j][k]+f[i-1][j][k])%mod;//不放 //一个 if(j>0) f[i][j][k]=(f[i][j][k]+f[i-1][j-1][k]*(m-k-(j-1)))%mod;//没有 if(k>0&&j
1) f[i][j][k]=(f[i][j][k]+f[i-1][j-2][k]*(m-k-(j-2))*(m-k-(j-2)-1)/2)%mod;//没有 if(j>0&&k>0) f[i][j][k]=(f[i][j][k]+f[i-1][j-1+1][k-1]*(m-(k-1)-j)*j)%mod;//一有一无 if(k>1&&j

 

 

转载于:https://www.cnblogs.com/AKCqhzdy/p/8446387.html

你可能感兴趣的文章
第六章实验报告(2)
查看>>
poj3294 出现次数大于n/2 的公共子串
查看>>
Android事件分发机制简述
查看>>
Embeded linux之各类文件系统
查看>>
链表问题(4)----环形链
查看>>
初入javascript知识点(七)
查看>>
C++ static成员变量与static成员函数
查看>>
十个开源深度学习框架
查看>>
004.MySQL双主+Keepalived高可用
查看>>
linux中安装nginx
查看>>
分布式之缓存系统
查看>>
Sandglass
查看>>
学习进度条15
查看>>
nodeJs建立简单的服务器
查看>>
Argument 'xxx' is not a function, got undefined,初学Angular的第一个坑
查看>>
【总结】LCA的4种求法
查看>>
热词解析(9) — hangry
查看>>
关于FBO(FrameBuffer Object)的一些理解
查看>>
学生信息管理系统小结
查看>>
Delphi之使用资源文件(Using Resource Files)
查看>>