洛谷 P2051 [AHOI2009]中国象棋 题解【DP】【递推】【分类讨论】
点击量: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;
}
说点什么