PEEK141 [SCOI2005]互不侵犯的国王

题目链接

PEEK141 [SCOI2005]互不侵犯的国王

题目描述

给定一个 N x N 的棋盘，要在上面放置 K 个国王，使得任意两个国王互相不攻击。国王的攻击范围是其周围的 8 个格子。请求出所有合法的摆放方案总数。

解题思路

这是一道经典的棋盘放置类组合计数问题，由于 N 的范围较小，非常适合使用状态压缩动态规划 (State Compression DP) 来解决。

核心思想：

我们按行（从上到下）在棋盘上放置国王。当我们决定第 i 行的布局时，只需要考虑它是否与第 i-1 行的布局冲突即可，因为国王的攻击范围只会延伸到相邻的行。这启发我们用动态规划来逐行构建解决方案。

1. 状态表示

由于 N 不大（通常 N <= 10），我们可以用一个 N 位的二进制数（即一个整数，也称为位掩码或 bitmask）来表示棋盘上一行中国王的摆放状态。如果该数的第 j 位是 1，表示在第 j 列放置了一个国王；如果是 0，则表示该位置为空。

基于此，我们可以定义一个三维的 DP 数组： dp[i][j][k]

其含义是：在前 i 行棋盘上，总共放置了 k 个国王，并且第 i 行的摆放状态由位掩码 j 表示时的合法方案总数。

2. 状态转移

dp[i][j][k] 的值可以通过累加第 i-1 行的所有有效状态得到。假设第 i-1 行的状态是 p，并且在前 i-1 行共放置了 k - count(j) 个国王（其中 count(j) 是状态 j 中国王的数量，即 j 的二进制表示中 1 的个数）。状态转移方程如下：

dp[i][j][k] = sum(dp[i-1][p][k - count(j)])

这个转移必须满足以下约束条件：

  • 行内合法性：当前第 i 行的状态 j 必须是合法的，即 j 中不能有两个国王相邻。用位运算可以表示为 (j & (j << 1)) == 0。

  • 行间合法性：当前第 i 行的状态 j 不能与上一行（第 i-1 行）的状态 p 发生冲突。这意味着 j 中的国王不能攻击到 p 中的国王。用位运算可以表示为：

    • 正上方不冲突: (j & p) == 0
    • 左上方不冲突: (j & (p << 1)) == 0
    • 右上方不冲突: (j & (p >> 1)) == 0

3. 优化与实现

直接在 DP 循环中遍历所有 2^N 个状态并判断其合法性效率不高。我们可以进行预处理：

  • 预处理合法状态：首先，遍历 0 到 2^N - 1 的所有整数，筛选出所有满足行内合法性（ (j & (j << 1)) == 0）的状态，将它们存入一个列表 states 中。同时，可以预计算每个合法状态包含的国王数量。
  • DP 过程：在进行 DP 时，我们只需要遍历这个预处理好的 states 列表，而不需要检查所有 2^N 个可能的状态。

4. 初始状态与最终答案

  • 初始状态：dp[0][0][0] = 1。这可以理解为一个虚拟的起点：在第 0 行，状态为 0（不放国王），总共放置 0 个国王，有 1 种方案。
  • 最终答案：放置 K 个国王的总方案数，等于在处理完所有 N 行后，总国王数为 K 的所有合法状态的方案数之和。即 sum(dp[N][j][K])，其中 j 遍历所有合法的单行状态。

代码

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

// 计算一个整数的二进制表示中 1 的个数
int countSetBits(int n) {
    int count = 0;
    while (n > 0) {
        n &= (n - 1);
        count++;
    }
    return count;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    cin >> n >> k;

    vector<int> states;
    vector<int> counts;

    // 预处理所有合法的单行状态
    for (int i = 0; i < (1 << n); ++i) {
        if ((i & (i << 1)) == 0) {
            states.push_back(i);
            counts.push_back(countSetBits(i));
        }
    }

    // dp[i][j][k]: 前 i 行，第 i 行状态为 j，共用 k 个国王的方案数
    vector<vector<vector<long long>>> dp(n + 1, vector<vector<long long>>(1 << n, vector<long long>(k + 1, 0)));

    dp[0][0][0] = 1;

    for (int i = 1; i <= n; ++i) {
        for (int j_idx = 0; j_idx < states.size(); ++j_idx) {
            int current_state = states[j_idx];
            int kings_in_current = counts[j_idx];
            
            for (int p_idx = 0; p_idx < states.size(); ++p_idx) {
                int prev_state = states[p_idx];

                // 检查行间冲突
                if ((current_state & prev_state) == 0 &&
                    (current_state & (prev_state << 1)) == 0 &&
                    (current_state & (prev_state >> 1)) == 0) {
                    
                    for (int total_k = kings_in_current; total_k <= k; ++total_k) {
                        dp[i][current_state][total_k] += dp[i - 1][prev_state][total_k - kings_in_current];
                    }
                }
            }
        }
    }

    long long ans = 0;
    for (int j_idx = 0; j_idx < states.size(); ++j_idx) {
        ans += dp[n][states[j_idx]][k];
    }

    cout << ans << endl;

    return 0;
}

import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();

        List<Integer> states = new ArrayList<>();
        List<Integer> counts = new ArrayList<>();

        for (int i = 0; i < (1 << n); i++) {
            if ((i & (i << 1)) == 0) {
                states.add(i);
                counts.add(Integer.bitCount(i));
            }
        }

        long[][][] dp = new long[n + 1][1 << n][k + 1];
        dp[0][0][0] = 1;

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < states.size(); j++) {
                int currentState = states.get(j);
                int kingsInCurrent = counts.get(j);

                for (int p = 0; p < states.size(); p++) {
                    int prevState = states.get(p);

                    if ((currentState & prevState) == 0 &&
                        (currentState & (prevState << 1)) == 0 &&
                        (currentState & (prevState >> 1)) == 0) {
                        
                        for (int totalK = kingsInCurrent; totalK <= k; totalK++) {
                            dp[i][currentState][totalK] += dp[i - 1][prevState][totalK - kingsInCurrent];
                        }
                    }
                }
            }
        }

        long ans = 0;
        for (int state : states) {
            ans += dp[n][state][k];
        }

        System.out.println(ans);
    }
}

import sys

def solve():
    try:
        n, k = map(int, sys.stdin.readline().split())
    except (IOError, ValueError):
        return

    states = []
    counts = []
    for i in range(1 << n):
        if (i & (i << 1)) == 0:
            states.append(i)
            counts.append(bin(i).count('1'))

    dp = [[[0] * (k + 1) for _ in range(1 << n)] for _ in range(n + 1)]
    dp[0][0][0] = 1

    for i in range(1, n + 1):
        for j_idx, current_state in enumerate(states):
            kings_in_current = counts[j_idx]
            for p_idx, prev_state in enumerate(states):
                if (current_state & prev_state) == 0 and \
                   (current_state & (prev_state << 1)) == 0 and \
                   (current_state & (prev_state >> 1)) == 0:
                    
                    for total_k in range(kings_in_current, k + 1):
                        dp[i][current_state][total_k] += dp[i-1][prev_state][total_k - kings_in_current]
    
    ans = 0
    for state in states:
        ans += dp[n][state][k]
        
    print(ans)

solve()

算法及复杂度

  • 算法：状态压缩动态规划 (State Compression DP)。
  • 时间复杂度：，其中 是满足行内约束的合法状态数量。 的数量级约等于斐波那契数列的第 N+2 项 。当 N=10 时，|S|=144，这个复杂度是完全可以接受的。
  • 空间复杂度：，用于存储 DP 状态数组。可以使用滚动数组优化到 。