专栏首页数据结构与算法P2051 [AHOI2009]中国象棋

P2051 [AHOI2009]中国象棋

题目描述

这次小可可想解决的难题和中国象棋有关,在一个N行M列的棋盘上,让你放若干个炮(可以是0个),使得没有一个炮可以攻击到另一个炮,请问有多少种放置方法。大家肯定很清楚,在中国象棋中炮的行走方式是:一个炮攻击到另一个炮,当且仅当它们在同一行或同一列中,且它们之间恰好 有一个棋子。你也来和小可可一起锻炼一下思维吧!

输入输出格式

输入格式:

一行包含两个整数N,M,之间由一个空格隔开。

输出格式:

总共的方案数,由于该值可能很大,只需给出方案数模9999973的结果。

输入输出样例

输入样例#1:

1 3

输出样例#1:

7

说明

样例说明

除了3个格子里都塞满了炮以外,其它方案都是可行的,所以一共有2*2*2-1=7种方案。

数据范围

100%的数据中N和M均不超过100

50%的数据中N和M至少有一个数不超过8

30%的数据中N和M均不超过6''

用dp[i][j][k]表示前i行,有j行放了一个,有k行放了两个

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<queue>
 6 #include<algorithm>
 7 using namespace std;
 8 const int MAXN=201;
 9 const int mod=9999973;
10 void read(int &n)
11 {
12     char c='+';int x=0;bool flag=0;
13     while(c<'0'||c>'9')
14     {c=getchar();if(c=='-')flag=1;}
15     while(c>='0'&&c<='9')
16     {x=x*10+c-48;c=getchar();}
17     flag==1?n=-x:n=x;
18 }
19 long long  dp[MAXN][MAXN][MAXN];
20 inline int C( int num ) 
21 { // 相当于C(num,2)
22     return num*(num-1)/2;
23 }
24 int n,m;
25 int main()
26 {
27     
28     read(n);read(m);
29     dp[0][0][0]=1;
30     for(int i=0;i<n;++i)
31         for(int j=0;j<=m;++j)
32             for(int k=0;k+j<=m;++k)
33                 if(dp[i][j][k]) 
34                 { 
35                        dp[i+1][j][k]=(dp[i+1][j][k]+dp[i][j][k])%mod; 
36                        if(m-j-k>=1) dp[i+1][j+1][k]=(dp[i+1][j+1][k]+dp[i][j][k]*(m-j-k))%mod; 
37                     if(j>=1) dp[i+1][j-1][k+1]=(dp[i+1][j-1][k+1]+dp[i][j][k]*j)%mod; 
38                     if(m-j-k>=2) dp[i+1][j+2][k]=(dp[i+1][j+2][k]+dp[i][j][k]*C(m-j-k))%mod; 
39                     if(m-j-k>=1&&j>=1) dp[i+1][j][k+1]=(dp[i+1][j][k+1]+dp[i][j][k]*(m-j-k)*j)%mod; 
40                     if(j>=2) dp[i+1][j-2][k+2]=(dp[i+1][j-2][k+2]+dp[i][j][k]*C(j))%mod; 
41                    }
42     long long ans=0;
43     for(int i=0;i<=m;++i)
44         for(int j=0;i+j<=m;++j)
45             ans=(ans+dp[n][i][j])%mod;
46     printf("%lld",ans);
47     return 0;
48 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • BZOJ 3450: Tyvj1952 Easy

    Description 某一天WJMZBMR在打osu~~~但是他太弱逼了,有些地方完全靠运气:( 我们来简化一下这个游戏的规则 有n次点击要做,成功了就是o...

    attack
  • P2327 [SCOI2005]扫雷

    题目描述 ? 输入输出格式 输入格式: 第一行为N,第二行有N个数,依次为第二列的格子中的数。(1<= N <= 10000) 输出格式: 一个数,即第一列中...

    attack
  • P1044 栈

    题目背景 栈是计算机中经典的数据结构,简单的说,栈就是限制在一端进行插入删除操作的线性表。 栈有两种最重要的操作,即pop(从栈顶弹出一个元素)和push(将一...

    attack
  • HDU 4632 Palindrome subsequence(区间DP)

    Palindrome subsequence Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 1...

    ShenduCC
  • 你的背包,被我找到了(0-1背包问题)

    给你一个可装载重量为W的背包和N个物品,每个物品有重量和价值两个属性。其中第i个物品的重量为wt[i],价值为val[i],现在让你用这个背包装物品,最多能装的...

    五分钟学算法
  • 告别动态规划,连刷40道动规算法题,我总结了动规的套路

    对于动态规划,春招秋招时好多题都会用到动态规划,一气之下,再 leetcode 连续刷了几十道动态规划的题

    乔戈里
  • 一道网易面试编程题

    一条长为n的路,需要用路灯点亮,其中"."表示需要点亮的位置,"X"表示无需点亮的位置,假设灯立在i处,则它可以点亮i-1,i,i+1三个位置,问至少需要多少灯...

    ShenduCC
  • 一天一大 leet(三角形最小路径和)难度:中等-Day20200715

    dp[i] = dp[0]xdp[i-1] + (dp[1]xdp[i-2]) + ... + (dp[i-2]xdp[1]) + dp[i-1]*dp[0]

    前端小书童
  • 动态规划该如何优化?我总结了这些套路,以后优化就是分分钟

    没错,80% 的动态规划题都可以画图,其中 80% 的题都可以通过画图一下子知道怎么优化,当然,DP 也有一些很难的题,想优化可没那么容易,不过,今天我要讲的,...

    乔戈里
  • 动态规划该如何优化?我总结了这些套路,以后优化就是分分钟

    前两天写一篇长达 8000 字的关于动态规划的文章告别动态规划,连刷40道动规算法题,我总结了动规的套路

    帅地

扫码关注云+社区

领取腾讯云代金券