欢迎访问~原文出处——博客园-zhouzhendong
去博客园看该题解
题目传送门 - BZOJ1801
题意概括
在N行M列的棋盘上,放若干个炮可以是0个,使得没有任何一个炮可以攻击另一个炮。 请问有多少种放置方法,中国像棋中炮的行走方式大家应该很清楚吧.
n,m<=100
题解
其实就是不出现3炮共线就可以了。
用dp[i][j][k]表示前i行,有j列还可以放1个跑,有k列还可以放2个跑的方案总数。
然后对于每一行,分别按照放0、1、2个炮进行转移。
放0个跑,那么就是:
dp[i+1][j][k]=(dp[i+1][j][k]+dp[i][j][k])%mod;
放1个,可以放在还可以放1个炮的列中,也可以放在还可以放2个炮的列中:
if (j>=1) dp[i+1][j-1][k]=(dp[i+1][j-1][k]+dp[i][j][k]*j)%mod;
if (k>=1) dp[i+1][j+1][k-1]=(dp[i+1][j+1][k-1]+dp[i][j][k]*k)%mod;
放2个,可以都放在还可以放1个炮的列中,也可以都放在还可以放2个炮的列中,也可以每边放一个:
if (j>=2) dp[i+1][j-2][k]=(dp[i+1][j-2][k]+dp[i][j][k]*(j*(j-1)/2))%mod;
if (k>=2) dp[i+1][j+2][k-2]=(dp[i+1][j+2][k-2]+dp[i][j][k]*(k*(k-1)/2))%mod;
if (j>=1&&k>=1)dp[i+1][j][k-1]=(dp[i+1][j][k-1]+dp[i][j][k]*j*k)%mod;
代码
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
typedef long long LL;
const int N=100+5;
const LL mod=9999973;
int n,m;
LL dp[N][N][N];
int main(){
scanf("%d%d",&n,&m);
memset(dp,0,sizeof dp);
dp[0][0][m]=1;
for (int i=0;i<n;i++)
for (int j=0;j<=m;j++)
for (int k=0;k+j<=m;k++){
if (!dp[i][j][k])
continue;
dp[i+1][j][k]=(dp[i+1][j][k]+dp[i][j][k])%mod;
if (j>=1)
dp[i+1][j-1][k]=(dp[i+1][j-1][k]+dp[i][j][k]*j)%mod;
if (k>=1)
dp[i+1][j+1][k-1]=(dp[i+1][j+1][k-1]+dp[i][j][k]*k)%mod;
if (j>=2)
dp[i+1][j-2][k]=(dp[i+1][j-2][k]+dp[i][j][k]*(j*(j-1)/2))%mod;
if (k>=2)
dp[i+1][j+2][k-2]=(dp[i+1][j+2][k-2]+dp[i][j][k]*(k*(k-1)/2))%mod;
if (j>=1&&k>=1)
dp[i+1][j][k-1]=(dp[i+1][j][k-1]+dp[i][j][k]*j*k)%mod;
}
LL ans=0;
for (int i=0;i<=m;i++)
for (int j=0;j<=m;j++)
ans=(ans+dp[n][i][j])%mod;
printf("%lld",ans);
return 0;
}
BZOJ1801 [Ahoi2009]chess 中国象棋 动态规划的更多相关文章
-
BZOJ1801 Ahoi2009 chess 中国象棋 【DP+组合计数】*
BZOJ1801 Ahoi2009 chess 中国象棋 Description 在N行M列的棋盘上,放若干个炮可以是0个,使得没有任何一个炮可以攻击另一个炮. 请问有多少种放置方法,中国像棋中炮的行 ...
-
BZOJ1801 [Ahoi2009]chess 中国象棋(DP, 计数)
题目链接 [Ahoi2009]chess 中国象棋 设$f[i][j][k]$为前i行,$j$列放了1个棋子,$k$列放了2个棋子的方案数 分6种情况讨论,依次状态转移. #include <b ...
-
bzoj1801: [Ahoi2009]chess 中国象棋(DP)
1801: [Ahoi2009]chess 中国象棋 题目:传送门 题解: 表示自己的DP菜的抠脚 %题解... 定义f[i][j][k]表示前i行 仅有一个棋子的有j列 有两个棋子的有k个 的方案数 ...
-
[luogu2051][bzoj1801][AHOI2009]chess中国象棋【动态规划】
题目描述 这次小可可想解决的难题和中国象棋有关,在一个N行M列的棋盘上,让你放若干个炮(可以是0个),使得没有一个炮可以攻击到另一个炮,请问有多少种放置方法.大家肯定很清楚,在中国象棋中炮的行走方式是 ...
-
BZOJ1801:[Ahoi2009]chess 中国象棋
Time Limit: 10 Sec Memory Limit: 64 MB Description 在N行M列的棋盘上,放若干个炮可以是0个,使得没有任何一个炮可以攻击另一个炮. 请问有多少种放置 ...
-
bzoj1801: [Ahoi2009]chess 中国象棋 dp
题意:在N行M列的棋盘上,放若干个炮可以是0个,使得没有任何一个炮可以攻击另一个炮. 请问有多少种放置方法,中国像棋中炮的行走方式大家应该很清楚吧. 题解:dp[i][j][k]表示到了第i行,有j列 ...
-
BZOJ1801 [Ahoi2009]chess 中国象棋 【dp】
题目 在N行M列的棋盘上,放若干个炮可以是0个,使得没有任何一个炮可以攻击另一个炮. 请问有多少种放置方法,中国像棋中炮的行走方式大家应该很清楚吧. 输入格式 一行包含两个整数N,M,中间用空格分开. ...
-
bzoj1801[AHOI2009]CHESS中国象棋
题意:在棋盘上放一些炮使得它们不互相攻击.其实就是一行/一列最多放两个. 50分的数据中n,m至少有一个不超过8,比较直接的想法是对n/m中较小的一维做状态压缩,状态f[i][S1][S2]表示在前i ...
-
【BZOJ1801】[Ahoi2009]chess 中国象棋 DP
[BZOJ1801][Ahoi2009]chess 中国象棋 Description 在N行M列的棋盘上,放若干个炮可以是0个,使得没有任何一个炮可以攻击另一个炮. 请问有多少种放置方法,中国像棋中炮 ...
随机推荐
-
浅谈JS继承
今天呢,我们来谈谈继承,它也是JS语言中的一大重点,一般什么时候我们会用继承呢,比如有两个拖拽的面板,两个功能基本一致,只是第二个面板多了一些不同的东西,这个时候,我们就会希望,要是第二个直接能继承第 ...
-
XML中的DOCTYPE属性
一.先来两个小例子 内部dtd将standalone设为真. <?xml version="1.0" standalone="yes"?> < ...
-
CP1W-CIF41以太网模块(使用总结)
1>插入CP1W-CIF41后,ERR灯一直闪烁? 解决方法:CIF41以太网模块在第一个扩展板槽位,需要把CP1H的4号拨码开关拨到ON的位置.同样,如果在第二个槽位,需要5号拨码拨到ON位置 ...
-
矩阵快速幂AC代码HDU 2035
#include <iostream> using namespace std;const int MOD = 1000;//像这样的一个常量就应该专门定义一下 int PowMod(in ...
-
ios 自定义NSError
from:[object-c错误处理]http://www.androiddev.net/objective-c%E5%AD%A6%E4%B9%A0%E4%B9%8B%E9%94%99%E8%AF%A ...
-
Python基础学习(第三周)
集合的操作 集合是一个无序的,不重复的数据组合,它的主要作用如下: 去重,把一个列表变成集合,就自动去重了 关系测试,测试两组数据之间的交集,差集,并集等关系 集合的写法 list_1 = set([ ...
-
CodeFroces-- 514.div2.C-Sequence Transformation
题目链接 :514.div2.C-Sequence Transformation #include<bits/stdc++.h> using namespace std; #define ...
-
Confluence 6 设置公共访问
你可以通过为匿名用户启用 'Use Confluence' 权限来启用匿名用户的站点访问(也称为公共访问) 一个匿名用户的定义为一个不需要登录就可以访问 Confluence 站点.使用 Conflu ...
-
AltiumDesigner17学习指南
AltiumDesigner工程模板 工程文件管理 视图->桌面布局->默认 恢复界面 AltiumDesigner17功能 修改元件标号 双击元件标号,在Designetor的Value ...
-
LG3690 【模板】Link Cut Tree (动态树)
题意 给定n个点以及每个点的权值,要你处理接下来的m个操作.操作有4种.操作从0到3编号.点从1到n编号. 0:后接两个整数(x,y),代表询问从x到y的路径上的点的权值的xor和.保证x到y是联通的 ...