[SCOI2005]互不侵犯 状压DP分析+题解

题目描述

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

输入格式

只有一行，包含两个数$N，K$ $（1<=N<=9,0<=K<=N\ast N）$

输出格式

所得的方案数

输入输出样例

输入 #1

3 2

输出 #1

16

题目分析

题目很短，分析之后可以写爆搜，但是强数据难免RE，因此考虑DP的做法。

N的范围小于等于9，那么典型的状压DP特征便表现出来了，实际上这是一道非常优质的状压DP入门题

下面对状压的过程进行详细的分析：首先什么是状压：

状压-即通过将状态压缩为整数来达到优化转移的目的。

对于本题，我们可以用一个二维数组来储存图，数组的对应位置表示棋盘上的实际位置，这事的状态并未进行压缩。

由于N的范围较小$(N<=9)$，我们可以很自然的反映出来：我们可以用二进制整数来表示每一行的状态，如图所示：

在上述的行状态下，我们通过一个八位二进制整数来表示了一行中各个位置的状态：10101010

既然这种方式成立，那么我们就可以根据二进制数各位表示的状态进行状态转移

了解了何为状压，接下来就是DP的分析

我们采用闫氏DP分析法进行分析：

状态转移方程的推导

首先，假设在第$i-1$行的的第$j$列放置一枚棋子，那么如图所示，第j行会出现不合法放置位置

即：第i行的$j-1,j,j+1$位置是非法的，那么在状压后如何对这些非法状态进行检测呢？相信你一定会立即反应出来：二进制运算

对于$j$位置的棋子，我们通过直接进行与运算进行检测，如果为1证明状态非法；

对于$j-1$位置的棋子，我们通过对L1左移进行检测(也可以对L2进行右移，原理相同)，如果为1证明状态非法；

对于$j+1$位置的棋子，我们通过对L1右移进行检测(也可以对L2进行左移，原理相同)，如果为1证明状态非法；

我们可以总结：当L2由L1进行转移时，必须满足的条件是：

(L2 & L1 == 0) && ((L2 << 1) & L1 == 0) && ((L2 >> 1) & L1 == 0)

化简得：

((L2|(L2 >> 1)|(L2 << 1)) & L1 == 0)

同时，第$i-1$行的$j-1,j+1$位置也是非法的，我们同样可以通过移位与运算进行检验：

合法的状态：

非法的状态：

满足条件：

((L << 1) | (L >> 1)) & L == 0

由于我们向下扫描递推，因此自上向下诞生合法状态，无需在考虑上一行是否合法。因此，下一步L2满足的状态我们全部总结完毕

因为第二个条件只与状态的情况有关，所以我们可以预处理这个东西，跑DP的时候将所有满足第二条性质的状态拿出来看看是否再满足第一条性质就好了；

设当前行的状态为 $j$ ，上一行的状态为 $x$ ，可以得到下面的转移方程： $f(i,j,l)=\sum f(i-1,x,l-sta(x))$ 。

AC Code

#include <bits/stdc++.h>
using namespace std;
long long sta[2005], sit[2005], f[15][2005][105];
int n, k, cnt = 0;
void dfs(int x, int num, int cur)
{
   
    if (cur >= n){
    // 有新的合法状态
        sit[++cnt] = x;
        sta[cnt] = num;
        return;
    }
    dfs(x, num, cur + 1); // cur位置不放国王
    dfs(x + (1 << cur), num + 1, cur + 2); // cur位置放国王，与它相邻的位置不能再放国王
}
int main()
{
   
    cin >> n >> k;
    dfs(0, 0, 0); // 先预处理一行的所有合法状态
    for (int i = 1; i <= cnt; i++)
        f[1][i][sta[i]] = 1;
    for (int i = 2; i <= n; i++)
        for (int j = 1; j <= cnt; j++)
            for (int l = 1; l <= cnt; l++){
   
                if (sit[j] & sit[l]) continue;
                if ((sit[j] << 1) & sit[l]) continue;
                if (sit[j] & (sit[l] << 1)) continue;
                // 排除不合法转移
                for (int p = sta[j]; p <= k; p++) f[i][j][p] += f[i - 1][l][p - sta[j]];
            }
    long long ans = 0;
    for (int i = 1; i <= cnt; i++) ans += f[n][i][k]; // 累加答案
    cout << ans << endl;
    return 0;
}