[Luogu P2051] [AHOI2009]中国象棋

题面

传送门:洛咕


Solution

看到这题,我们不妨先看一下数据范围

$30pt:n,m<=6$
显然搜索,直接爆搜水过
复杂度$O(n^m(吧))$

.

$50pt: n<=100,m<=8$

是状压/网络流的复杂度

当然,这题显然是状压

由题可以得出一个很显然但很重要的废话:每行每列只能放0~2个棋子

因此,我们可以考虑写一个3进制的状压DP

设$f[i][j]$表示第 $i$ 行,每一列的具体情况以三进制的表达形式存在$j$里 的方案数

转移也很显然

分类转移一下

当前这一行放了0个棋子 $f[i][j]+=f[i-1][j]$

当前这一行放了1个棋子, 枚举一下有可能放的位置k $f[i][j]+=\sum f[i-1][k]$

当前这一行放了2个棋子 ,枚举一下那两个有可能放的位置,最后表达成k $f[i][j]+=\sum f[i-1][k]$

初始化$f[0][0]=1$,最后答案为 $\sum f[n][i]$

复杂度$O(n*(3^m))$

.

$100pt:n,m<=100$

其实之前50分做法离正解已经很接近了

再仔细思考(手玩)一下,就会发现答案与每一列棋子摆放位置无关

也就是说我们根本就没必要具体记录每一列的具体情况,只需要记录有多少列放了1个棋,有多少列放了2个棋

设$f[i][j][k]$表示第i行时有j列放了1个棋,有k列放了2个棋

然后转移和上面基本上没什么区别,具体请看代码

.

初始化$f[0][0][0]=1$.答案为$\sum f[n][i][j]$

复杂度$O(nmm)$


Code

//Luogu P2051 [AHOI2009]中国象棋
//May,8th,2018
//状压转网格DP
#include<iostream>
#include<cstdio>
using namespace std;
long long read()
{
    long long x=0,f=1; char c=getchar();
    while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
const int N=100+10;
const int poi=9999973;
long long f[N][N][N];
int n,m;
int main()
{
    n=read(),m=read();

    f[0][0][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++)
        {
            int MAX_K=m-j;
            for(int k=0;k<=MAX_K;k++)
            {
                f[i][j][k]+=f[i-1][j][k];//放0个棋子
                if(j>=1) f[i][j][k]=(f[i][j][k]+f[i-1][j-1][k]*(m-k-j+1))%poi;//放1个棋子,且放在原本为0的列
                if(k>=1) f[i][j][k]=(f[i][j][k]+f[i-1][j+1][k-1]*(j+1))%poi;//放1个棋子,且放在原本为1的列
                if(j>=2) f[i][j][k]=(f[i][j][k]+f[i-1][j-2][k]*(((m-j-k+1)*(m-j-k+2))/2))%poi;//放2个棋子,且都放在原本为0的列
                if(j>=1 and k>=1) f[i][j][k]=(f[i][j][k]+f[i-1][j][k-1]*(j*(m-j-k+1)))%poi;//放2个棋子,一个放在0,一个放在1
                if(k>=2) f[i][j][k]=(f[i][j][k]+f[i-1][j+2][k-2]*(((j+1)*(j+2))/2))%poi;//放2个棋子,都放在原本为1的列
            }
        }

    long long ans=0;
    for(int i=0;i<=m;i++)
    {
        int MAX_J=m-i;
        for(int j=0;j<=MAX_J;j++)
            ans=(ans+f[n][i][j])%poi;
    }
    printf("%lld",ans);
    return 0;
}
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注