P8756 [蓝桥杯 2021 省 AB2] 国际象棋 题解

· · 题解

原题传送门

Part 0

这是一道状态压缩 \text{DP}。

在尝试此题之前，建议大家先去完成 P1896 [SCOI2005] 互不侵犯，与此题类似，可以让大家对状态压缩 \text{DP} 有一个初步的了解，也为此题作铺垫。

注：这篇题解并不会非常详细地去讲解状态压缩的原理，只是在 P1896 的基础上来解决此题。

Part 1

这一题中，需要我们求在 N \times M (1 \leq N \leq 6, 1 \leq M \leq 100) 的棋盘上摆 K (1 \leq K \leq 20) 个马的方案数。由于 N 不超过 6，我们先枚举每一列的 2 ^ N 个放马方案，用 1 表示放马， 0 表示不放，并统计每一个放法中 1 的个数（也就是马的个数）。到此为止，做法与 P1896 完全相同。

接下来就是转移状态了。P1896 中只需考虑前一行的状态，所以用 位置、方案、个数 来表示答案。而本题需要考虑前两行的状态，需要多加一维，以 位置、前列方案、本列方案、个数 来表示答案。

然后通过五层循环 位置、本列方案、个数、前列方案、前前列方案 来进行状态转移。注意：这里要判断三行中会不会有马互相攻击。最后别忘把答案对 10^9 + 7 取模。

AC Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int mxn = 100, mxm = 1 <<6;
const int N = mxn + 10, M = mxm + 10;
int n, m, K, num[M], dp[N][M][M][30], ans;
int get_val(int x) {
    int sum = 0;
    while(x) sum += x & 1, x >>= 1;
    return sum;
} // 求出马的个数
signed main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m >> K;
    for(int i = 0; i ^ (1 << n); ++ i) num[i] = get_val(i), dp[1][0][i][num[i]] = 1; // 预处理马的个数
    for(int i = 2; i <= m; ++ i) // 列
        for(int j = 0; j ^ (1 << n); ++ j) // 本列状态
            for(int h = num[j]; h <= K; ++ h) // 马的个数
                for(int k = 0; k ^ (1 << n); ++ k) // 前前列状态
                    for(int l = 0; l ^ (1 << n); ++ l) // 前列状态
                        if(! ((j & (k << 1)) || (j & (k >> 1)) || (j & (l << 2)) || (j & (l >> 2)) || (l & (k << 2)) || (l & (k >> 2)))) // 判断条件是否满足
                            dp[i][l][j][h] = (dp[i][l][j][h] + dp[i - 1][k][l][h - num[j]]) % mod; //进行转移
    for(int i = 0; i ^ (1 << n); ++ i)
        for(int j = 0; j ^ (1 << n); ++ j)
            ans = (ans + dp[m][i][j][K]) % mod;
    cout << ans << '\n';
    return 0;
}