题面
传送门:https://www.luogu.org/problemnew/show/P2051
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]+=xigema f[i-1][k]
当前这一行放了2个棋子 ,枚举一下那两个有可能放的位置,最后表达成k f[i][j]+=xigema f[i-1][k]
初始化f[0][0]=1,最后答案为 xigema 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.答案为 xigema f[n][i][j]
复杂度O(n*m*m)
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;
}
正解(C++)