BZOJ1801 [Ahoi2009]chess 中国象棋 动态规划

时间:2021-12-13 06:17:13

欢迎访问~原文出处——博客园-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 中国象棋 动态规划的更多相关文章

  1. BZOJ1801 Ahoi2009 chess 中国象棋 【DP&plus;组合计数】&ast;

    BZOJ1801 Ahoi2009 chess 中国象棋 Description 在N行M列的棋盘上,放若干个炮可以是0个,使得没有任何一个炮可以攻击另一个炮. 请问有多少种放置方法,中国像棋中炮的行 ...

  2. BZOJ1801 &lbrack;Ahoi2009&rsqb;chess 中国象棋(DP, 计数)

    题目链接 [Ahoi2009]chess 中国象棋 设$f[i][j][k]$为前i行,$j$列放了1个棋子,$k$列放了2个棋子的方案数 分6种情况讨论,依次状态转移. #include <b ...

  3. bzoj1801&colon; &lbrack;Ahoi2009&rsqb;chess 中国象棋(DP)

    1801: [Ahoi2009]chess 中国象棋 题目:传送门 题解: 表示自己的DP菜的抠脚 %题解... 定义f[i][j][k]表示前i行 仅有一个棋子的有j列 有两个棋子的有k个 的方案数 ...

  4. &lbrack;luogu2051&rsqb;&lbrack;bzoj1801&rsqb;&lbrack;AHOI2009&rsqb;chess中国象棋【动态规划】

    题目描述 这次小可可想解决的难题和中国象棋有关,在一个N行M列的棋盘上,让你放若干个炮(可以是0个),使得没有一个炮可以攻击到另一个炮,请问有多少种放置方法.大家肯定很清楚,在中国象棋中炮的行走方式是 ...

  5. BZOJ1801&colon;&lbrack;Ahoi2009&rsqb;chess 中国象棋

    Time Limit: 10 Sec  Memory Limit: 64 MB Description 在N行M列的棋盘上,放若干个炮可以是0个,使得没有任何一个炮可以攻击另一个炮. 请问有多少种放置 ...

  6. bzoj1801&colon; &lbrack;Ahoi2009&rsqb;chess 中国象棋 dp

    题意:在N行M列的棋盘上,放若干个炮可以是0个,使得没有任何一个炮可以攻击另一个炮. 请问有多少种放置方法,中国像棋中炮的行走方式大家应该很清楚吧. 题解:dp[i][j][k]表示到了第i行,有j列 ...

  7. BZOJ1801 &lbrack;Ahoi2009&rsqb;chess 中国象棋 【dp】

    题目 在N行M列的棋盘上,放若干个炮可以是0个,使得没有任何一个炮可以攻击另一个炮. 请问有多少种放置方法,中国像棋中炮的行走方式大家应该很清楚吧. 输入格式 一行包含两个整数N,M,中间用空格分开. ...

  8. bzoj1801&lbrack;AHOI2009&rsqb;CHESS中国象棋

    题意:在棋盘上放一些炮使得它们不互相攻击.其实就是一行/一列最多放两个. 50分的数据中n,m至少有一个不超过8,比较直接的想法是对n/m中较小的一维做状态压缩,状态f[i][S1][S2]表示在前i ...

  9. 【BZOJ1801】&lbrack;Ahoi2009&rsqb;chess 中国象棋 DP

    [BZOJ1801][Ahoi2009]chess 中国象棋 Description 在N行M列的棋盘上,放若干个炮可以是0个,使得没有任何一个炮可以攻击另一个炮. 请问有多少种放置方法,中国像棋中炮 ...

随机推荐

  1. 浅谈JS继承

    今天呢,我们来谈谈继承,它也是JS语言中的一大重点,一般什么时候我们会用继承呢,比如有两个拖拽的面板,两个功能基本一致,只是第二个面板多了一些不同的东西,这个时候,我们就会希望,要是第二个直接能继承第 ...

  2. XML中的DOCTYPE属性

    一.先来两个小例子 内部dtd将standalone设为真. <?xml version="1.0" standalone="yes"?> < ...

  3. CP1W-CIF41以太网模块(使用总结)

    1>插入CP1W-CIF41后,ERR灯一直闪烁? 解决方法:CIF41以太网模块在第一个扩展板槽位,需要把CP1H的4号拨码开关拨到ON的位置.同样,如果在第二个槽位,需要5号拨码拨到ON位置 ...

  4. 矩阵快速幂AC代码HDU 2035

    #include <iostream> using namespace std;const int MOD = 1000;//像这样的一个常量就应该专门定义一下 int PowMod(in ...

  5. 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 ...

  6. Python基础学习(第三周)

    集合的操作 集合是一个无序的,不重复的数据组合,它的主要作用如下: 去重,把一个列表变成集合,就自动去重了 关系测试,测试两组数据之间的交集,差集,并集等关系 集合的写法 list_1 = set([ ...

  7. CodeFroces-- 514&period;div2&period;C-Sequence Transformation

    题目链接 :514.div2.C-Sequence Transformation #include<bits/stdc++.h> using namespace std; #define ...

  8. Confluence 6 设置公共访问

    你可以通过为匿名用户启用 'Use Confluence' 权限来启用匿名用户的站点访问(也称为公共访问) 一个匿名用户的定义为一个不需要登录就可以访问 Confluence 站点.使用 Conflu ...

  9. AltiumDesigner17学习指南

    AltiumDesigner工程模板 工程文件管理 视图->桌面布局->默认 恢复界面 AltiumDesigner17功能 修改元件标号 双击元件标号,在Designetor的Value ...

  10. LG3690 【模板】Link Cut Tree (动态树)

    题意 给定n个点以及每个点的权值,要你处理接下来的m个操作.操作有4种.操作从0到3编号.点从1到n编号. 0:后接两个整数(x,y),代表询问从x到y的路径上的点的权值的xor和.保证x到y是联通的 ...