P2051 [AHOI2009] 中国象棋 个人题解

题目链接

题目描述：

给你一个 \(n*m\) 的棋盘，棋盘的每行和每列只能放置有 \(2\) 个棋子（可以放置 \(0\) 个棋子），问有多少种放置方案

解题方法：

这道题看起来像是八皇后问题的加强版，但是如果一个个枚举的话，复杂度将是天文数字，可以发现这是在有限集合内求最优解的问题，我们使用 DP 来解决，下面用闫氏 DP 分析法来考虑状态转移方程。

状态表示：

集合：我们用 \(f[i][j][k]\) 表示所有前 \(i\) 行有 \(j\) 列放置了一个棋子且有 \(k\) 列放置了两个棋子的方案数集合

属性：MAX

状态计算：

1. 当前第 \(i\) 行一个棋子也不放时

由上一行也就是第 \(i-1\) 行的状态直接转移过来：
\(f[i][j][k]=f[i-1][j][k]\)

2. 当前第 \(i\) 行放置一个棋子时

此时分为两种情况，一种是选择空列放置时，另一种是选择已经放置一个棋子的列。

1° 当选择空列放置时

由第 \(i-1\) 行，有 \(j-1\) 列放置了一个棋子且有 \(k\) 列放置了两个棋子的方案数转移过来，为什么是 \(j-1\) 而不是 \(j\) 呢？因为如果我们在一个空列上新放一个棋子，那么就会新产生有一个棋子的一列，而我们当前的状态为 \(f[i][j][k]\) ，所以是从 \(f[i-1][j-1][k]\) 转移过来，注意到此时一共有 \(m-(j-1)-k\) 个空列，所以方案数要加上 \(f[i-1][j-1][k]*(m-(j-1)-k)\) ,即此时的状态转移方程为：
\(f[i][j][k]+=f[i-1][j-1][k]*(m-(j-1)-k)\)

2°当选择已经放置一个棋子的列时

由第 \(i-1\) 行，有 \(j+1\) 列放置了一个棋子且有 \(k-1\) 列放置了两个棋子的方案数转移过来，与上面一样都是根据当前的状态，在放到已经放置了一个棋子的列上后，这一列变成放置了两个棋子的列，所以是从 \(f[i-1][j+1][k-1]\) 转移过来，此时一共有 \(j+1\) 列放置了一个棋子的列，即共有 \(j+1\) 种可能m,则此时的状态转移方程为;
\(f[i][j][k]+=f[i-1][j+1][k-1]*(j+1)\)

3. 当前第 \(i\) 行放置两个棋子时

此时分为三种情况，一种时都选择空列位置，一种是都选择已经放置一个棋子的列，还有一种是一个棋子选择空列，另一个棋子选择已经放置一个棋子的列。

1°当都选择空列放置时

由第 \(i-1\) 行，有 \(j-2\) 列放置了一个棋子且有 \(k\) 列放置了两个棋子的方案数转移过来，此时共有 \(m-(j-2)-k\) 个空列，而要放置两个棋子则选择数为

\[\begin{pmatrix} 2\\ m-(j-2)-k \\\end{pmatrix} \]

则此时的状态转移方程为：
\(f[i][j][k]+=f[i-1][j-2][k]*\begin{pmatrix} 2\\ m-(j-2)-k \\\end{pmatrix}\)

2°当都选择已经放置一个棋子的列时

由第 \(i-1\) 行，有 \(j+2\) 列放置了一个棋子且有 \(k-2\) 列放置了两个棋子的方案数转移过来，此时共有 \(j+2\) 个已经放置一个棋子的列，而要放置两个棋子则选择数为

\[\begin{pmatrix} 2\\ j+2 \\\end{pmatrix} \]

则此时的状态转移方程为：
\(f[i][j][k]+=f[i-1][j+2][k-2]*\begin{pmatrix} 2\\ j+2 \\\end{pmatrix}\)

3°当一个棋子选择空列，另一个棋子选择已经放置一个棋子的列时

由第 \(i-1\) 行，有 \(j\) 列放置了一个棋子且有 \(k-1\) 列放置了两个棋子的方案数转移过来，此时共有 \(m-j-(k-1)\) 个空列和 \(j\) 个已经放置一个棋子的列，故选择数为 \(j*(m-j-(k-1)))\)
则此时的状态转移方程为：
\(f[i][j][k]+=f[i-1][j-2][k]*j*(m-j-(k-1))\)

综上，我们得到完整的状态转移方程：

1°一个也不选：\(f[i][j][k]=f[i-1][j][k]\)
2°只选一个棋子：\(\begin{cases}f[i][j][k]+=f[i-1][j-1][k]*(m-(j-1)-k) & 选择空列\\f[i][j][k]+=f[i-1][j+1][k-1]*(j+1) & 选择已经有一个棋子的列\end{cases}\)
3°选择两个棋子：\(\begin{cases}f[i][j][k]+=f[i-1][j-2][k]*\begin{pmatrix} 2\\ m-(j-2)-k \\\end{pmatrix} & 都选择空列\\f[i][j][k]+=f[i-1][j+2][k-2]*\begin{pmatrix} 2\\ j+2 \\\end{pmatrix} & 都选择已经有一个棋子的列\\f[i][j][k]+=f[i-1][j-2][k]*j*(m-j-(k-1)) & 一个棋子选择空列，另一个棋子选择已经放置一个棋子的列\end{cases}\)
最后开始状态为 \(f[0][0][0]=1\) ，因为如果不放棋子的话也算一种方案，最终答案为 $$\sum_{i=0,j=0}^{m}f[n][i][j]$$，最后别忘记结果要 \(\bmod 9999973\)

代码如下: