中国象棋
2019-08-16 07:49:52来源:博客园 阅读 ()
中国象棋
中国象棋
题目
【题目描述】
这次小可可想解决的难题和中国象棋有关,在一个N行M列的棋盘上,让你放若干个炮(可以是0个),使得没有一个炮可以攻击到另一个炮,请问有多少种放置方法。
大家肯定很清楚,在中国象棋中炮的行走方式是:一个炮攻击到另一个炮,当且仅当它们在同一行或同一列中,且它们之间恰好 有一个棋子。
你也来和小可可一起锻炼一下思维吧!
【输入格式】
一行包含两个整数N,M,之间由一个空格隔开。
【输出格式】
总共的方案数,由于该值可能很大,只需给出方案数模9999973的结果。
【数据规模】
100%的数据中N和M均不超过100
50%的数据中N和M至少有一个数不超过8
30%的数据中N和M均不超过6
解析
动态规划题。
令f[i][j][k]表示前i行,放一个炮的有j列,放两个炮的有k列,边界为f[0][0][0]=1,,
则状态转移方程有以下几种:
1、不放:f[i][j][k]=f[i][j][k]+f[i-1][j][k];
2、放一个在零个的那列:f[i][j][k]=f[i][j][k]+f[i-1][j-1][k]*(m-j-k+1);
3、放一个在一个的那列:f[i][j][k]=f[i][j][k]+f[i-1][j+1][k-1]*(j+1);
4、分别放一个在一个的两列:f[i][j][k]=f[i][j][k]+f[i-1][j+2][k-2]*(j+1)*(j+2)/2;
5、分别放一个在零个的一列和一个的一列:f[i][j][k]=f[i][j][k]+f[i-1][j][k-1]*j*(m-j-k+1);
6、分别放一个在零个的两列:f[i][j][k]=f[i][j][k]+f[i-1][j-2][k]*(m-j-k+1)*(m-j-k+2)/2。
要注意各种情况的先决条件!最后的答案是所有f[n][j][k]的总和。记得开long long!!!
Code
#include <algorithm> #include <iostream> #include <cstring> #include <string> #include <cstdio> #include <cmath> using namespace std; const int mod=9999973; int n,m; long long f[101][101][101],ans; //f[i][j][k]表示前i行,放一个炮的有j列,放两个炮的有k列 int main() { memset(f,0,sizeof(f)); cin>>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<=m-j;k++) { f[i][j][k]=(f[i][j][k]+f[i-1][j][k])%mod;//不放 if(j)//放一个在零个的那列 f[i][j][k]=(f[i][j][k]+f[i-1][j-1][k]*(m-j-k+1))%mod;//(m-j-k+1)即原来零个的总列数 if(k)//放一个在一个的那列 f[i][j][k]=(f[i][j][k]+f[i-1][j+1][k-1]*(j+1))%mod;//(j+1)即原来一个的总列数 if(k>=2)//分别放一个在一个的两列 f[i][j][k]=(f[i][j][k]+f[i-1][j+2][k-2]*(j+1)*(j+2)/2)%mod;//(j+2)即原来有两列为一个的总列数 if(j&&k)//分别放一个在零个的一列和一个的一列 f[i][j][k]=(f[i][j][k]+f[i-1][j][k-1]*j*(m-j-k+1))%mod; if(j>=2)//分别放一个在零个的两列 f[i][j][k]=(f[i][j][k]+f[i-1][j-2][k]*(m-j-k+1)*(m-j-k+2)/2)%mod; } for(int j=0;j<=m;j++) for(int k=0;k<=m-j;k++) ans=(ans+f[n][j][k])%mod;//累加答案 cout<<ans; return 0; }View Code
原文链接:https://www.cnblogs.com/I-Love-You-520/p/11187691.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:树形DP求树的直径
- P1358 扑克牌 2020-05-06
- 博弈--巴什博弈 2020-04-24
- Z 字形变换 2020-04-14
- [题记-并查集] 合根植物 - 蓝桥杯 2020-04-07
- 无法正确通过算法题目都是哪些原因造成的? 2020-04-05
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash