洛谷 P2051 [AHOI2009]中国象棋 题解【DP】【递推】【分类讨论】

作者: wjyyy 分类: DP,分类讨论,解题报告,递推 发布时间: 2018-06-19 19:52

点击量:180

 

   世界杯期间是不是应该出一道中国足球呢23333333

 

题目描述

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

 

输入输出格式

输入格式:

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

 

输出格式:

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

 

输入输出样例

输入样例#1:
1 3
输出样例#1:
7

说明

样例说明

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

 

数据范围

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

 

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

 

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

 

30pts做法:


对于N,M≤6的情况,有36个格子,枚举状态有$ 2^{36}$种,有点悬,加上剪枝6×6还是过不去。常数大的话,只要把6×6打表输出,这30分就比较稳了,注意模9999973。

 

50pts做法:


因为有一维的长度是≤8的,我们只要把这一维当作宽(长宽交换不影响),就可以做两位一压/三进制的状压DP,所需数字大小为$ 2^16=65536$,时间上稍微注意一下就是能当普通的状压DP做了。

 

100pts递推+动态规划+分类讨论:


   我们注意到,在上面一维一维推下来的状态中,每一列分为3种状态:没放过,放了1个,放了2个。

 

   对于没有放的列,我们就可以在当前行的那一列放一个。而如果有u个没有放的列,就有u种方案了。根据递推,我们在当前状态上加上用u乘上上一列有u列没有放时的方案数

 

   对于放了1个的,我们也可以在当前行的那一列放一个。同理我们如果只管在各个放了一个的列(设有v个)上只放一枚炮,同上,在当前状态下加上用v乘上上一列有v列没有放时的方案数

 

   如果某一列已经放了两个,那么它就不能再放了,相当于这个状态已经被转移完毕了。

 

   我们对当前行来看,当前行最多只能放2个。我们回头来看最基础的情况:如果当前行什么都不放,就是f[i][j][k]=f[i-1][j][k]。

 

   对于放2个的情况:尽管当前列已经转移过放1个的情况,但是这样同一行的状态是乱的,我们继续分类讨论,按照上一行的状态递推下来。

 

   对上一行的已经满了的列(放过2个炮),就不能转移;非满的列有三种情况:分别放0,0(指两个没放过炮的列);1,0;0,1;1,1。

 

  • 0,0的状态是将上一行的2个不同的放置次数为0的列变成次数为1的列,状态种类是在上一行放置次数为0的状态个数(设为u)中,任取两个0的方案数,即$ C_u^2 =(u-1)\times u$,不过要去重除以2。

 

  • 1,1的状态是将上一行2个不同的放置次数为1的列变成次数为2的列,状态种类是上一行放置次数为1的状态的个数(v)中任取两个,为$ C_v^2 =(v-1)\times v$,同样要去重除以2。

 

  • 0,1的状态也是类似的,将上一行两个放置次数为0和1的,分别改为1和2,根据乘法原理(以上都是乘法原理)状态种类为u×v,这里u和v没有重复的,所以不用去重。

 

   这样我们整理完状态后,构造状态转移方程。设f[i][j][k]表示第i行有j个没放过的,k个放过一个的(此时放过两个的就是m-k-j)方案个数。

 

   我们如果由上面一行推过来,状态会比较整齐,个数不变的还是不变;个数为1的增加了,同时个数为0的减少了就用j那一维减去,用k那一维加上:f[i][j][k]=f[i-1][j-1][k+1]。同理其他也是这样递推的,关于放掉的第四维也是直接与二三维的下标有关,只用管数组的二三维即可。(详细的方程代码里也比较整齐)

 

   分类讨论的思想,对于一道题的状态,如果有很多种本质相同的情况,我们就可以考虑分类讨论。因为我们只管它的系数,而不管它的具体位置,这种情况下就可以考虑分类讨论,最后只要乘一下原状态的个数就行了。

 

   这样的一个毒瘤DP题就差不多整完了。然而$ 9999973\times 9999973\approx 10^{14}$,中途状态会爆int,所以dp数组还是要开long long的。


Code:

#include<cstring>
#include<cstdio>
long long f[105][105][105];
//f[i,j,k]表示在第i行结束后,有j列放了0枚炮,有k列放了1枚(m-k-j列放了2枚)
int main()
{
    memset(f,0,sizeof(f));
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        f[0][m][0]=1;
    for(int i=1;i<=n;i++)
    {
        //对于每一行 枚举j,k
        for(int j=0;j<=m;j++)
            for(int k=0;k<=m-j;k++)
            {
                f[i][j][k]=f[i-1][j][k]%9999973;//什么也不放,一种方案
                if(k)
                    f[i][j][k]+=f[i-1][j+1][k-1]*(j+1)%9999973;//放一枚炮在原来放了0处
                f[i][j][k]+=f[i-1][j][k+1]*(k+1)%9999973;//放一枚炮在原来放了1处
                f[i][j][k]%=9999973;
                if(k-1)//防止越界到-1
                    f[i][j][k]+=(f[i-1][j+2][k-2]*(j+2)*(j+1)/2)%9999973;//放两枚炮在原来都为0处
                f[i][j][k]+=(f[i-1][j][k+2]*(k+2)*(k+1)/2)%9999973;//放两枚炮在原来都为1处
                f[i][j][k]+=f[i-1][j+1][k]*(j+1)*k%9999973;//放两枚炮在原来分别为0,1处
                f[i][j][k]%=9999973;
            }
    }
    long long ans=0;
    for(int j=0;j<=m;j++)
        for(int k=0;k<=m-j;k++)
        {
            ans+=f[n][j][k];
            ans%=9999973;
        }
    printf("%lld\n",ans);
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */