[洛谷P2051] [AHOI2009]中国象棋
洛谷题目链接:[AHOI2009]中国象棋
题目描述
这次小可可想解决的难题和中国象棋有关,在一个N行M列的棋盘上,让你放若干个炮(可以是0个),使得没有一个炮可以攻击到另一个炮,请问有多少种放置方法。大家肯定很清楚,在中国象棋中炮的行走方式是:一个炮攻击到另一个炮,当且仅当它们在同一行或同一列中,且它们之间恰好 有一个棋子。你也来和小可可一起锻炼一下思维吧!
输入输出格式
输入格式:
一行包含两个整数N,M,之间由一个空格隔开。
输出格式:
总共的方案数,由于该值可能很大,只需给出方案数模9999973的结果。
输入输出样例
输入样例#1:
1 3
输出样例#1:
7
说明
样例说明
除了3个格子里都塞满了炮以外,其它方案都是可行的,所以一共有222-1=7种方案。
数据范围
100%的数据中N和M均不超过100
50%的数据中N和M至少有一个数不超过8
30%的数据中N和M均不超过6
一句话题意: 一个矩阵中填入一些炮,使得任意两个炮不能互相打到.
题解: 如果玩过象棋就会知道,一行最多只能放入两个炮.看这个数据范围,可以想到DP.
那么该如何设置状态呢?
一开始我有个错误的思路,我用\(f[i][j][k][l]\)表示到第\(i\)行第\(j\)列的位置,在第\(i\)行放了\(k\)个炮,第\(j\)行放了\(l\)个炮,\((k,l \in [0,2])\).但是这样显然是错误的.因为有些状态是重复的,那么在统计答案的时候就无法计算总数.
那么该如何改进呢?
显然什么棋子放入格子的时间与最终答案是没有影响的,最后的答案只和棋子放在哪些位置有关.但是这个位置事实上也是只需要用来考虑合法方案数的,也就是说我并不需要知道每个炮具体是放在哪个位置,我只需要知道这一行还能够放入几个来对答案作贡献.
我们设状态\(f[i][j][k]\)表示到第\(i\)行,有\(j\)列放了1个棋子,有\(k\)列放了2个棋子.那么在新枚举一行的时候,就会有这样的情况:
- 这一行不放棋子.
- 放一个棋子放在没有棋子的一列.
- 放一个棋子放在已经放了一个棋子的一列.
- 放两个棋子都放在没有棋子的两列.
- 放一个棋子在没有棋子的一列,再放一个棋子放在有一个棋子的一列.
- 两个棋子都放在有一个棋子的一列.
那么这些状态都是可以对当前这一行的答案做出贡献的,在枚举的时候把这些状态都加进来就可以了.
#include<bits/stdc++.h>
using namespace std;
const int N=100+5;
const int yyj=9999973;
typedef int _int;
#define int long long
int n, m, f[N][N][N], ans = 0;
_int main(){
ios::sync_with_stdio(false);
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;j+k<=m;k++){
(f[i][j][k] += f[i-1][j][k]) %= yyj;
if(j) (f[i][j][k] += f[i-1][j-1][k]*(m-k-j+1)) %= yyj;
if(k) (f[i][j][k] += f[i-1][j+1][k-1]*(j+1)) %= yyj;
if(j >= 2) (f[i][j][k] += f[i-1][j-2][k]*(m-j-k+2)*(m-j-k+1)/2) %= yyj;
if(k >= 2) (f[i][j][k] += f[i-1][j+2][k-2]*(j+2)*(j+1)/2) %= yyj;
if(k) (f[i][j][k] += f[i-1][j][k-1]*(m-j-k+1)*j) %= yyj;
}
for(int i=0;i<=m;i++)
for(int j=0;j<=m;j++)
(ans += f[n][i][j]) %= yyj;
cout << ans << endl;
return 0;
}
最新文章
- jQuery Mobile入门
- ios开发中遇到的编译错误总结
- ajax 跨域提交数据
- 如何获取客户端MAC地址(三个方法)
- 前端开发必须知道的JS(二) 闭包及应用
- buffer pool
- c3p0的log4j配置
- 【highcharts】
- ↗☻【编写可维护的JavaScript #BOOK#】第8章 避免“空比较”
- WPF异步调用WCF服务
- Swift - 数组排序方法(附样例)
- C语言 二维数组复制、清零及打印显示
- linux文件权限查看及修改-chmod ------入门的一些常识
- 【JSOI2008】星球大战 (并查集)
- MySQL实战45讲学习笔记:索引(第四讲)
- 二十六、css3改变checkbox复选框的样式
- 《DRN: A Deep Reinforcement Learning Framework for News Recommendation》强化学习推荐系统
- TypeScript 版本相关
- vue内置组件 transition 和 keep-alive 使用
- CANOE入门(二)