G状压 DP

棋盘 / 轮廓状压

互不侵犯·炮兵阵地

本课摘要

棋盘 / 轮廓状压课程回答“逐行棋盘约束怎样编码为兼容位掩码”。内容以互不侵犯·炮兵阵地为主线，配合逐步推导、可编辑演示、例题与练习形成可复查的学习闭环。

判断棋盘 / 轮廓状压的适用条件与状态边界
围绕“互不侵犯·炮兵阵地”推导转移与计算顺序
用演示、复杂度分析和配套题目校验实现

本课目录 · 0 节

正在整理目录…

当「一行的选择」有了 2ⁿ 种

先看一个具体问题：在 $3\times 3$ 的棋盘上放国际象棋的王，王会攻击周围 8 格，要求两两互不攻击，问放 2 个王有多少种方案。如果一行一行地放，每一行的状态无非是「哪些列放了王」——这本身就是 $2^3=8$ 种可能。

为什么不能像线性 DP 那样，只记「这一行放了几个王」？因为下一行能不能放，不只取决于个数，还取决于放在哪些列——两个王只要斜对角相邻就冲突。「几个」这个标量丢掉了列的信息，是有后效性的。我们需要把「这一行的完整摆法」原封不动地记进状态里。

一行棋盘「放 / 不放」正好对应一个二进制整数 mask——第 c 列放了王，就让第 c 位是 1。

关键的一步：把一整行的摆法压成一个整数。第 $c$ 列放了王就让二进制第 $c$ 位为 $1$ ，否则为 $0$ 。于是「列 1、列 3 放了王」就是 $00101_2=5$ 。整行的 $2^n$ 种摆法，一一对应 $0$ 到 $2^n-1$ 这些整数——这就是状态压缩：用一个 mask 承载一行的全部信息。

这类「逐行推进、把当前行压成 mask」的状压，叫棋盘状压 / 轮廓状压。它只在 $n$ 很小（通常 $\le 12$ ）时可行，因为每行要枚举 $2^n$ 种摆法。

两道判定：行内合法、行间合法

压成 mask 之后，「合不合法」全部变成位运算——这正是状压的威力。放王有两条约束：

① 行内不相邻。同一行里两个王不能挨着（左右相邻会互相攻击）。把摆法 $x$ 左移一位再和自己按位与： $x\ \&\ (x{<}{<}1)$ 。若结果非 $0$ ，说明存在某位和它左边一位同时为 1，即有相邻——不合法。合法当且仅当 $x\ \&\ (x{<}{<}1)=0$ 。

② 行间不冲突。本行 $x$ 与上一行 $y$ ，王会攻击正下、左下、右下三个方向。用三个按位与一起判：正上方 $x\ \&\ y$ 、左上 $x\ \&\ (y{<}{<}1)$ 、右上 $x\ \&\ (y{>}{>}1)$ ，三者全为 $0$ 才合法。

行内用 x&(x<<1) 查横向相邻；行间用 x&y 等查上下同列/斜角冲突（虚线为冲突列）。

有了判定，状态与转移就顺理成章。设 $f[r][j][x]$ 表示：前 $r$ 行、一共放了 $j$ 个王、且第 $r$ 行摆法为 $x$ 时的方案数。转移枚举上一行摆法 $y$ ：

f[r][j][x]=\sum_{y\,\sim\,x} f[r-1][\,j-\mathrm{popcount}(x)\,][y]

其中记号 $y\sim x$ 表示上一行摆法 $y$ 与本行 $x$ 兼容—— $y$ 行内合法、且与 $x$ 行间不冲突。边界：第 1 行 $f[1][\mathrm{popcount}(x)][x]=1$ 。答案： $\sum_x f[n][K][x]$ 。

本质

状压把「一行的组合结构」塞进一个整数，于是合法性判定 = 一两条位运算、状态转移 = 枚举相邻两行的 mask 配对。指数级的摆法被 $O(n\cdot K\cdot 4^n)$ 的表格容纳——只在 $n$ 小才划算，这也是状压的适用边界。

跟着算一遍

用 $3\times 3$ 棋盘、放 $K=2$ 个王，把方程跑几步。先列出「行内合法」的一行摆法（ $n=3$ ）：

摆法 101（列 1、列 3）——两个 1 不相邻，行内合法；而 011、110 因相邻被淘汰。

枚举行内合法摆法。

n=3

的 8 种里，去掉含相邻 1 的（

011,110,111

），剩

000,001,010,100,101

共 5 种。其中放了 2 个王的只有

101

。

第 1 行初始化。 每个合法摆法各算 1 种：

f[1][0][000]=1

、

f[1][1][001]=1

、…、

f[1][2][101]=1

。

第 2 行接上。 想让第 2 行摆

x=101

：它要放 2 个王，需

j\ge 2

；上一行

y

必须和它行间不冲突。

y=101

时

x\&y=101\ne 0

冲突；只有

y=000

才兼容 →

f[2][2][101]\mathrel{+}=f[1][0][000]=1

。

累到第 3 行求和。 把

f[3][2][x]

对所有

x

求和，就得到

3\times 3

放 2 个互不攻击的王的方案数（答案是

16

）。

下面的演示会在棋盘上逐行放王，先带你看「其中一种」合法布局怎么一行行搭起来，再一键用状压 DP 算出方案总数。改 N 和 K 试试。

逐行放王，再数尽所有方案

目标：在 4×4 棋盘放 4 个互不攻击的王。逐行确定每行摆法。

进度

已暂停，第 1 步，共 6 步，1 倍速

当攻击「隔两格」：状态升到两行

互不侵犯里，冲突只发生在相邻行之间，所以状态记住「上一行」就够了。可一旦攻击范围更远，一行就不够了——炮兵阵地就是典型：炮兵沿行、列方向攻击两格，于是同一列上，第 $i$ 行的炮兵会打到第 $i-1$ 行和第 $i-2$ 行。

要判断新一行合不合法，必须同时知道前两行的摆法。状态因此升维成 $f[i][x][y]$ ——第 $i$ 行摆 $x$ 、第 $i-1$ 行摆 $y$ ；转移再枚举第 $i-2$ 行的 $z$ ，要求 $x\&y=x\&z=y\&z=0$ （三行两两同列不撞）。

炮兵攻击隔两格：新行要同时避开 i−1 与 i−2 两行，所以状态必须携带「前两行」的 mask。

同行内部也更严：两个炮兵至少隔 $3$ 列，判定变成 $x\&(x{<}{<}1)=0$ 且 $x\&(x{<}{<}2)=0$ 。这一步「从记一行升到记两行」，是轮廓状压最常见的进阶跳板——状态里到底要留几行，取决于约束能跨多远。

常见陷阱：合法 mask 要预处理，别每次重算

$n\le 10$ 时合法摆法只有几十个，务必先枚举一遍存进数组（连同它的 $\mathrm{popcount}$ ），转移时只在这几十个之间配对。若在四重循环里对全部 $2^n$ 现算判定，炮兵那种三行枚举会直接超时。这是棋盘状压能否通过的关键工程点。

例题

P1896[SCOI2005] 互不侵犯SCOI2005普及+/提高

题意

N\times N

棋盘放

K

个王，王攻击相邻 8 格，求两两互不攻击的放置方案数（

N\le 9

）。

为什么选它

棋盘状压的「最小完整模型」：行内 $x\&(x{<}{<}1)$ + 行间 $x\&y$ 双判定一次讲透，还带「已放王数」这一维练计数。是本类的立骨题。

状态 · 转移 · 复杂度

f[r][j][x]

=前

r

行放

j

个、末行摆

x

的方案数；枚举兼容的上一行

y

累加。复杂度

O(N\cdot K\cdot M^2)

，

M

为合法摆法数。

参考代码

C++

在洛谷打开 P1896

#include <iostream>
using namespace std;

long long f[10][2005][1 << 9];   // f[行][已放王数][本行摆法mask]
int st[600], num[600], cnt;      // 预处理：行内合法的 mask 及其王数

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

    for (int s = 0; s < (1 << n); s++)      // 枚举一行所有摆法
    {
        if (s & (s << 1)) continue;         // ★行内：相邻两列都放则丢弃
        st[cnt] = s;
        num[cnt] = __builtin_popcount(s);   // 这行放了几个王
        cnt++;
    }

    for (int i = 0; i < cnt; i++)           // 第 1 行：直接填
        if (num[i] <= K)
            f[1][num[i]][st[i]] = 1;

    for (int r = 2; r <= n; r++)            // 逐行递推
        for (int i = 0; i < cnt; i++)       // 本行摆法
            for (int j = num[i]; j <= K; j++)
                for (int p = 0; p < cnt; p++) // 上一行摆法
                {
                    int a = st[i], b = st[p];
                    if (a & b) continue;        // ★正上方相邻
                    if (a & (b << 1)) continue; // ★左上相邻
                    if (a & (b >> 1)) continue; // ★右上相邻
                    f[r][j][a] += f[r - 1][j - num[i]][b];
                }

    long long ans = 0;
    for (int i = 0; i < cnt; i++)
        ans += f[n][K][st[i]];
    cout << ans << endl;
    return 0;
}

P1879[USACO06NOV] Corn Fields GUSACO 2006普及+/提高

题意

M\times N

田地，部分格贫瘠不可种，且相邻格不能都种，求（含一块都不种的）种植方案数，对

10^8

取模。

换个视角

比互不侵犯多了「禁格」：把每行不可种的格压成掩码

g[i]

，一行摆法

x

合法当且仅当

x\&g[i]=0

。位运算判定极干净，是「带禁格的棋盘状压」范本。

参考代码

C++

在洛谷打开 P1879

#include <iostream>
using namespace std;

const int MOD = 1e8;
int g[15];                        // g[i]：第 i 行的「贫瘠格」掩码（1=不能种）
int f[15][1 << 12];
int st[5000], cnt;                // 行内合法（无横向相邻）的 mask

int main()
{
    int m, n;
    cin >> m >> n;
    for (int i = 1; i <= m; i++)
        for (int j = 0; j < n; j++)
        {
            int x; cin >> x;
            if (x == 0) g[i] |= (1 << j);   // 0 = 不可种 → 记入贫瘠掩码
        }

    for (int s = 0; s < (1 << n); s++)
        if (!(s & (s << 1))) st[cnt++] = s; // 行内无相邻

    f[0][0] = 1;                            // 第 0 行（虚拟空行）方案数 1
    for (int i = 1; i <= m; i++)
        for (int a = 0; a < cnt; a++)
        {
            int s = st[a];
            if (s & g[i]) continue;         // ★踩到贫瘠格，非法
            for (int b = 0; b < cnt; b++)
            {
                int t = st[b];
                if (s & t) continue;        // 上下相邻同列不能都种
                f[i][s] = (f[i][s] + f[i - 1][t]) % MOD;
            }
        }

    int ans = 0;
    for (int a = 0; a < cnt; a++)
        ans = (ans + f[m][st[a]]) % MOD;
    cout << ans << endl;
    return 0;
}

P2704[NOI2001] 炮兵阵地NOI2001提高+/省选-

题意

N\times M

地图（

M\le 10

），部分为山地不可驻扎；炮兵沿行列攻击两格，求最多能驻扎多少炮兵互不攻击。

为什么选它

把状态从「一行」升到「前两行」的经典进阶：

f[i][x][y]

记末两行摆法，转移枚举第三行。它逼你想清「状态要留几行」这个轮廓状压的核心问题。

参考代码

C++

在洛谷打开 P2704

#include <iostream>
#include <algorithm>
using namespace std;

int g[105];                       // g[i]：第 i 行山地(H)掩码，1=不能放
int st[105], num[105], cnt;       // 行内合法：任意两个 1 至少隔 2 列
int f[105][105][105];             // f[行][上一行mask下标][上上行mask下标]

bool ok(int s)                    // 同行炮兵间隔 ≥ 3（攻击隔两格）
{
    return !(s & (s << 1)) && !(s & (s << 2));
}

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < m; j++)
        {
            char c; cin >> c;
            if (c == 'H') g[i] |= (1 << j);
        }

    for (int s = 0; s < (1 << m); s++)
        if (ok(s)) { st[cnt] = s; num[cnt] = __builtin_popcount(s); cnt++; }

    for (int i = 1; i <= n; i++)
        for (int a = 0; a < cnt; a++)       // 本行
        {
            if (st[a] & g[i]) continue;
            for (int b = 0; b < cnt; b++)   // 上一行
            {
                if (st[a] & st[b]) continue;
                for (int c = 0; c < cnt; c++)   // 上上行
                {
                    if (st[a] & st[c]) continue;
                    if (st[b] & st[c]) continue;
                    f[i][a][b] = max(f[i][a][b],
                                     f[i - 1][b][c] + num[a]);
                }
            }
        }

    int ans = 0;
    for (int a = 0; a < cnt; a++)
        for (int b = 0; b < cnt; b++)
            ans = max(ans, f[n][a][b]);
    cout << ans << endl;
    return 0;
}

练习

P2622关灯问题 II把灯的开关状态压成 mask，每个按钮是一次「异或若干位」的操作，求从全亮到全灭的最少按压——状压 + BFS 最短步。在洛谷打开

P2915[USACO08NOV] Mixed Up Cows G排列型状压：f[S][i]=用完集合 S 的奶牛、末位是 i 的合法排列数，转移要求相邻编号差 > K。与 TSP 同构。在洛谷打开

P3694邦邦的大合唱站队每个人属于某乐队，把「已归位的乐队集合」压成 mask，f[S]=让 S 中乐队各自连续所需最少移出人数，枚举下一个整块乐队。在洛谷打开

想亲手试试？到 G 部分页的「棋盘布阵」手动放王，实时看位运算判定冲突，再点「看 DP 全部方案数」对照。