跳到主要内容

互不侵犯

信息

此题目来自 洛谷， 原始题目与提交代码请前往 P1896 [SCOI2005] 互不侵犯 - 洛谷。

题目描述​

在 N×N{N}\times{N} 的棋盘里面放 KK 个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共 88 个格子。

输入格式​

只有一行，包含两个数 N,KN,K。

输出格式​

所得的方案数

输入输出样例​

输入 #1

3 2

输出 #1

16

说明/提示​

对于全部数据，1≤N≤9{1}\le{N}\le{9}，0≤K≤N×N{0}\le{K}\le{{N}\times{N}}。

题目解答​

这是一道十分经典的状压 DP 的题目。 既然它是一道动态规划的题目，免不了状态转移方程。

位运算​

本题解涉及到了位运算 &、|、>>、<<。

& 的作用是只让两个数据都有 1 的位置输出 1。 比如说 0 & 0 = 0、0 & 1 = 0、1 & 0 = 0、1 & 1 = 1。

| 的作用是让其中一个数据有 1 的位置输出 1。 比如说 0 & 0 = 0、0 & 1 = 1、1 & 0 = 1、1 & 1 = 1。

>> 的作用左边数据的数据移动右边数据指定的步数，而 << 与其用法类似。 比如说 010 >> 1 = 001、100 & 2 = 001。

定义方程​

我们来定义一个方程 dp[i][si][ki]dp[i][s_i][k_i]， 其中

  • ii (index) 是行的序列数/索引
  • sis_i (state) 是行的状态
  • kik_i (king counts) 是此行放置了的国王数量

对于 sis_i，其值使用二进制来表示。 比如我现在有一个 3×3{3}\times{3} 棋盘 (其中一种情况)：

123
1👑👑
2
3👑

我们按照定义来用表格表示这个方程：

iisis_ikik_idp[i][si][ki]dp[i][s_i][k_i]
110000011
110101111
111012211
2200011 或 2222
220101111
221012211
…\dots...…\dots…\dots

推导方程​

为了方便表示皇冠四周没有更多的皇冠，我们用一个集合 SS 包含所有可能的 sis_i：

S={0≤si<2N,si&(si≪1)=0}S=\left\{ 0\le{s_i}<{2^N}, \\ {s_i}\&({s_i}\ll{1})=0 \right\}

本质上就是两个条件：

  • 0≤si<2N0\le{s_i}<{2^N}：状态码的长度不可能超过 NN，否则没有意义。
  • 在 si&(si≪1)=0{s_i}\&({s_i}\ll{1})=0 中
    • si≪1{s_i}\ll{1} (假设为 si′{s_{i}}') 将所有皇冠左移了 1 单位长度，
    • si&si′{s_i}\&{s_{i}}' 中，若皇冠间只有 1 单位长度，si′{s_{i}}' 在和位运算时会将与空位对应，那么位运算完成后，每一位都应当为 00。

我们先从第 11 行开始看起，不难发现，第一行的摆放不受其它行的影响， 同时，只要我们确保其摆放的合规的，那么其状态转移方程应为：

dp[0][s0][k0]=1dp[0][s_0][k_0] = 1

考虑到上面的皇冠可能收到下面皇冠的攻击，即皇冠上方的左边、中间、右边都不能有皇冠。 整行被放满皇冠的棋盘可以表示为 1≪N)−1{1}\ll{N})-{1}，即当 N=3N=3，其结果就为 111。 接着，我们在皇冠周围框出一个水平区域 si∣si≪1∣si≫1{s_i}|{s_i}\ll{1}|{s_i}\gg{1}， 合在一起，(si∣si≪1∣si≫1)&(1≪N)−1){({s_i}|{s_i}\ll{1}|{s_i}\gg{1})}\&{({1}\ll{N})-{1})} ，那么就选择出来了皇冠不能放置的区域。 再与 si−1s_{i-1} 和位运算，理想中应该为 00。 因而 sis_i 与 si−1s_{i-1} 要符合 si−1&((si∣si≪1∣si≫1)&(1≪N)−1))=0{s_{i-1}}\&{({({s_i}|{s_i}\ll{1}|{s_i}\gg{1})}\&{({1}\ll{N})-{1})})}=0。

此后的第 ii 行的状态转移方程都为：

dp[i][si][ki]={∑si−1∈S,si−1&((si∣si≪1∣si≫1)&(1≪N)−1))=0dp[i−1][si−1][ksi−1−ki],0dp[i][s_i][k_i] = { \left\{ \begin{matrix} \sum\limits_{{s_{i-1}}\in{S},{s_{i-1}}\&{({({s_i}|{s_i}\ll{1}|{s_i}\gg{1})}\&{({1}\ll{N})-{1})})}=0}^{} dp[i-1][s_{i-1}][k_{s_{i-1}}-k_i], \\ 0 \end{matrix}\right. }

为什么是 ksi−1k_{s_{i-1}} ？ 其含义为此时第 i−1i-1 行中符合题目条件 (即皇冠四周不能有皇冠) 的状态下，那个状态的 kk 的值，也就是皇冠数量。

同时，∑si−1∈S,si−1&((si∣si≪1∣si≫1)&(1≪N)−1))=0dp[i−1][si−1][ksi−1−ki]\sum\limits_{{s_{i-1}}\in{S},{s_{i-1}}\&{({({s_i}|{s_i}\ll{1}|{s_i}\gg{1})}\&{({1}\ll{N})-{1})})}=0}^{} dp[i-1][s_{i-1}][k_{s_{i-1}}-k_i] 也很好理解。 dp[i−1][si−1][ksi−1−ki]dp[i-1][s_{i-1}][k_{s_{i-1}}-k_i] 即第 i−1i-1 行在 si−1s_{i-1} 状态下 (该值不唯一) 方案数量。 那么 ∑si−1∈S,si−1&((si∣si≪1∣si≫1)&(1≪N)−1))=0dp[i−1][si−1][ksi−1−ki]\sum\limits_{{s_{i-1}}\in{S},{s_{i-1}}\&{({({s_i}|{s_i}\ll{1}|{s_i}\gg{1})}\&{({1}\ll{N})-{1})})}=0}^{} dp[i-1][s_{i-1}][k_{s_{i-1}}-k_i] 与第 ii、i−1i-1 行所有符合题意的方案之和。

因而，总方案数应为：

总方案数=∑sN−1∈Sdp[N−1][sN−1][K]\text{总方案数}=\sum_{{s_{N-1}}\in{S}} dp[N-1][s_{N-1}][K] 
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

int main() {
    int N, K;
    cin >> N >> K;

    const int full_mask = (1 << N) - 1;

    vector<int> state_list;
    for (int s = 0; s <= full_mask; s++) {
        // 检查行内是否有相邻国王：(s & (s << 1)) == 0
        if ((s & (s << 1)) == 0) {
            state_list.push_back(s);
        }
    }
    int num_states = state_list.size();  // 有效状态数量

    vector<int> state_count(num_states);    // 每个状态的国王数
    vector<int> forbid_mask(num_states);    // 每个状态的禁用手码
    
    for (int i = 0; i < num_states; i++) {
        int s = state_list[i];
        state_count[i] = __builtin_popcount(s);
        forbid_mask[i] = (s | (s << 1) | (s >> 1)) & full_mask;
    }

    vector<vector<int>> compatible(num_states);
    for (int i = 0; i < num_states; i++) {
        for (int j = 0; j < num_states; j++) {
            // 检查状态兼容性：t & P(s) == 0
            if ((state_list[j] & forbid_mask[i]) == 0) {
                compatible[i].push_back(j);  // j状态是i状态的兼容上一行状态
            }
        }
    }

    // dp[i][k] = 方案数，其中i是状态索引，k是国王总数
    vector<vector<long long>> dp(num_states, vector<long long>(K + 1, 0));
    
    // 初始化第一行
    for (int i = 0; i < num_states; i++) {
        int cnt = state_count[i];
        if (cnt <= K) {
            dp[i][cnt] = 1;  // 有效状态设置方案数为1
        }
    }

    for (int row = 1; row < N; row++) {
        // 创建新DP表
        vector<vector<long long>> new_dp(num_states, vector<long long>(K + 1, 0));
        
        for (int cur_idx = 0; cur_idx < num_states; cur_idx++) {
            int cur_count = state_count[cur_idx];  // 当前行国王数
            
            for (int total_k = cur_count; total_k <= K; total_k++) {
                // 计算前一行的国王数
                int prev_k = total_k - cur_count;
                
                // 遍历所有兼容的上一行状态
                for (int prev_idx : compatible[cur_idx]) {
                    if (prev_k >= 0) {
                        new_dp[cur_idx][total_k] += dp[prev_idx][prev_k];
                    }
                }
            }
        }
        
        dp = move(new_dp);  // 更新DP表
    }

    long long ans = 0;
    for (int i = 0; i < num_states; i++) {
        ans += dp[i][K];  // 累加所有状态中放置K个国王的方案
    }
    
    cout << ans << endl;

    return 0;
}