G状压 DP

状压 + 覆盖

愤怒的小鸟·宝藏

本课摘要

状压 + 覆盖课程回答“几何覆盖选择怎样预处理成可转移的状态集合”。内容以愤怒的小鸟·宝藏为主线，配合逐步推导、可编辑演示、例题与练习形成可复查的学习闭环。

  • 判断状压 + 覆盖的适用条件与状态边界
  • 围绕“愤怒的小鸟·宝藏”推导转移与计算顺序
  • 用演示、复杂度分析和配套题目校验实现
本课目录 · 0 节

正在整理目录…

当「一步」能盖住一批元素

TSP 里，走一步只到达一个新点。但很多问题里，一次「选择」能一口气覆盖一批元素：一条抛物线砸下去打掉好几只猪、按一个开关翻转好几盏灯、修一条路连通好几个城市。目标不再是「排好顺序」，而是「用最小代价把全部元素覆盖掉」。

先看一个抽象的小例子：全集有 5 个元素 {0,1,2,3,4}\{0,1,2,3,4\}，有若干「选择」，每个选择覆盖其中一部分、各有代价。要选出一组选择，让它们的覆盖并起来等于全集，总代价最小。这就是集合覆盖——它是 NP 难的，但当元素个数 n≤20n\le 20 时，状压给出可行解。

选择 A11000选择 B00110选择 C00001并集11111= 11111 = 全集 (1<<5)−1 → 覆盖完成
每个选择覆盖的元素压成一个 mask；若干 mask 按位或起来，填满全集 (1<<5)−1 就算覆盖完成。

关键的预处理：把每个选择「覆盖了哪些元素」压成一个 mask。于是「加入一个选择」就是把当前已覆盖集合 SS 和这个选择的 mask 做按位或——SS 只会变大或不变，永远单调朝全集靠拢。「覆盖满」就是 S=(1<<n)−1S=(1{<}{<}n)-1。

状态与转移：dp[S] = 覆盖 S 的最小代价

定状态。这里的集合 SS 含义变了——不再是 TSP 的「已访问点」，而是「已被覆盖的元素」。设 dp[S]dp[S] = 让 SS 里所有元素都被覆盖所需的最小代价。注意状态只有一维，没有「当前点」——因为覆盖问题不关心顺序。

转移。从 dp[S]dp[S] 出发，选第 kk 个选择（覆盖 mask 记 ckc_k、代价 wkw_k），新覆盖集合是 S ∣ ckS\ |\ c_k：

dp[ S ∣ ck ]=min⁡(dp[S ∣ ck], dp[S]+wk)dp[\,S\ |\ c_k\,]=\min\big(dp[S\ |\ c_k],\ dp[S]+w_k\big)

边界：dp[0]=0dp[0]=0（什么都没覆盖，代价 0），其余 +∞+\infty。答案：dp[(1<<n)−1]dp[(1{<}{<}n)-1]。按 SS 从小到大枚举即可，因为 S ∣ ck≥SS\,|\,c_k\ge S，依赖的子状态先算好。

0111213141
目标态：全集 (1<<n)−1（全 1）。dp 从 dp[0]=0 出发，每次按位或把 S 推向这一格，取到它的最小代价即答案。

本质

状压把「覆盖进度」编码成一个整数：「还差哪些没盖」一目了然，「加一个选择」就是一次按位或。TSP 的 dp[S][i]dp[S][i] 关心「停在哪」，覆盖的 dp[S]dp[S] 只关心「盖到哪」——同样是 2n2^n 个集合状态，少一维。预处理每个选择的覆盖 mask，是这类题的题眼。

跟着算一遍

用 4 个元素的小例子：选择 A 覆盖 {0,1}\{0,1\} 代价 2、B 覆盖 {2,3}\{2,3\} 代价 2、C 覆盖全部 {0,1,2,3}\{0,1,2,3\} 代价 5。看 dpdp 怎么填：

01112030
选择 A 的覆盖 mask = 0011（元素 0、1）；顶端为元素编号。
0
起点。 dp[0000]=0dp[0000]=0，其余全设 +∞+\infty。
1
从空集用 A。 0000 ∣ 0011=00110000\ |\ 0011=0011：dp[0011]=min⁡(∞,0+2)=2dp[0011]=\min(\infty,0+2)=2。同理用 B 得 dp[1100]=2dp[1100]=2，用 C 得 dp[1111]=5dp[1111]=5。
2
在 A 的基础上用 B。 S=0011S=0011 时再选 B：0011 ∣ 1100=11110011\ |\ 1100=1111，dp[1111]=min⁡(5, dp[0011]+2)=min⁡(5,4)=4dp[1111]=\min(5,\ dp[0011]+2)=\min(5,4)=4。A+B 组合（代价 4）比单用 C（代价 5）更省。
3
读答案。 dp[1111]=4dp[1111]=4——覆盖全集的最小代价。状压自动比较了「一步全覆盖」和「拼图式组合」两条路。
下面的演示把 dp[S]dp[S] 按集合从小到大排成一排。改选择的覆盖范围和代价，看每一步按位或如何把覆盖推向全集，终态取到最小代价。

看覆盖一步步填满全集

选择（点元素格切换是否覆盖 · 调代价）· 全集 = {0,1,2,3}
选择 A
代价2
选择 B
代价2
选择 C
代价5
0
∞
∞
2
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
用选择 A：从已覆盖 0000（代价 0）并入它覆盖的元素 → 变成 0011。 新代价 = 2，原 dp[0011] = ∞ → 更新为 2。
已暂停，第 1 步，共 7 步，1 倍速
终态 1111（全集）的最小代价 = 4。

状压不止 TSP：从覆盖到「逐层生成树」

集合覆盖让我们看清：状压的 SS 可以是任何「一批东西的选取状态」，转移的核心是用按位或把 SS 变大。顺着这条路，「宝藏」（P3959）把状压推得更远——它求的是一棵生成树的最小代价，边权 = 深度 × 长度。

它的状态是 f[dep][S]f[dep][S]：已经连成的点集为 SS、当前生成树最大深度为 depdep 的最小代价。转移时，从已连通的 SS 向外「长一层」——枚举 SS 补集的一个子集作为新接入的点，每个新点用「它到 SS 的最短边 × 当前深度」计费。这里既用到覆盖式的按位或扩展，又要枚举子集（下一类的核心技巧）。

常见陷阱：覆盖 mask 的预处理别算错、别漏

愤怒的小鸟里，两点定一条抛物线要求横坐标不同、开口朝下（a<0a<0），还要用浮点误差 ε\varepsilon 判点是否落在线上——漏判或精度不当会让某条线的覆盖 mask 出错，答案随之全错。稳妥的骨架是：先固定「第一只还没打的猪」 pp，再枚举过 pp 的所有抛物线去覆盖，避免重复与遗漏。

例题

P2831[NOIP2016 提高组] 愤怒的小鸟NOIP2016提高+/省选-
题意
平面上 nn 只猪（n≤18n\le 18），每发小鸟沿一条过原点、开口朝下的抛物线飞行，砸掉线上所有猪，求打光所有猪的最少发数。
为什么选它
集合覆盖的标杆题：教学点「两点定抛物线 → 预处理这条线覆盖哪些猪（压成 mask）」极其清晰。dp[S]dp[S]=打掉集合 SS 的最少发数，转移选一条线做按位或。
状态 · 转移 · 复杂度
dp[S ∣ line]=min⁡(⋅,dp[S]+1)dp[S\,|\,line]=\min(\cdot,dp[S]+1)；固定第一只未打的猪减少枚举。O(2n⋅n)O(2^n\cdot n)（外加 O(n2)O(n^2) 预处理）。
参考代码
C++
在洛谷打开 P2831 
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

const double EPS = 1e-6;
int T, n, m;
double X[20], Y[20];
int line[20][20];               // line[i][j]：过点 i、j 的抛物线能打掉的猪 mask
int f[1 << 18];

int main()
{
    cin >> T;
    while (T--)
    {
        cin >> n >> m;
        for (int i = 0; i < n; i++) cin >> X[i] >> Y[i];
        memset(line, 0, sizeof line);

        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
            {
                if (fabs(X[i] - X[j]) < EPS) continue;      // 竖直，无法定抛物线
                // 由 (X[i],Y[i])、(X[j],Y[j]) 解 y=a x^2 + b x（过原点）
                double a = (Y[i] / X[i] - Y[j] / X[j]) / (X[i] - X[j]);
                double b = Y[i] / X[i] - a * X[i];
                if (a > -EPS) continue;                     // 开口必须朝下
                int s = 0;
                for (int k = 0; k < n; k++)                 // ★这条线覆盖哪些猪
                    if (fabs(a * X[k] * X[k] + b * X[k] - Y[k]) < EPS)
                        s |= (1 << k);
                line[i][j] = s;
            }

        memset(f, 0x3f, sizeof f);
        f[0] = 0;
        for (int S = 0; S < (1 << n); S++)
        {
            if (f[S] == 0x3f3f3f3f) continue;
            int p = 0;
            while (p < n && (S >> p & 1)) p++;              // 找第一只没打的猪 p
            if (p == n) continue;
            f[S | (1 << p)] = min(f[S | (1 << p)], f[S] + 1); // 单点一发
            for (int j = 0; j < n; j++)                     // 选一条过 p 的抛物线
                f[S | line[p][j]] = min(f[S | line[p][j]], f[S] + 1);
        }
        cout << f[(1 << n) - 1] << endl;
    }
    return 0;
}
P3959[NOIP2017 提高组] 宝藏NOIP2017提高+/省选-
题意
nn 个点、mm 条带权边（n≤12n\le 12），选一点为根建生成树，一条边的开采代价 = 边权 × 它到根的层数，求最小总代价。
换个视角
展示「状压不止 TSP」：状态 f[dep][S]f[dep][S] 记「已连通点集 + 当前深度」，转移逐层把补集的子集接进来。它同时用到「按位或扩展」和「枚举子集」，是承上启下的一题。
参考代码
C++
在洛谷打开 P3959 
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int n, m;
int road[15][15];               // 两点间道路长度（无边为 INF）
int cost[1 << 12][15];          // cost[S][j]：从集合 S 向外接一步到 j 的最小边权
int f[13][1 << 12];             // f[dep][S]：已连成集合 S、最大深度 dep 的最小代价

int main()
{
    memset(road, 0x3f, sizeof road);
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int a, b, c; cin >> a >> b >> c;
        a--; b--;
        road[a][b] = road[b][a] = min(road[a][b], c);
    }

    // 预处理：集合 S 之外的点 j，到 S 的最短单边
    for (int S = 0; S < (1 << n); S++)
        for (int j = 0; j < n; j++)
        {
            if (S >> j & 1) continue;
            int mn = 0x3f3f3f3f;
            for (int i = 0; i < n; i++)
                if ((S >> i & 1) && road[i][j] < mn) mn = road[i][j];
            cost[S][j] = mn;
        }

    memset(f, 0x3f, sizeof f);
    for (int i = 0; i < n; i++) f[1][1 << i] = 0;   // 任一点单独作根，深度 1

    for (int dep = 2; dep <= n; dep++)
        for (int S = 1; S < (1 << n); S++)
        {
            if (f[dep - 1][S] == 0x3f3f3f3f) continue;
            int rest = ((1 << n) - 1) ^ S;              // S 外的点
            // ★枚举 rest 的非空子集 sub，作为这一层新接入的点
            for (int sub = rest; sub; sub = (sub - 1) & rest)
            {
                int w = 0; bool ok = true;
                for (int j = 0; j < n; j++)
                    if (sub >> j & 1)
                    {
                        if (cost[S][j] == 0x3f3f3f3f) { ok = false; break; }
                        w += cost[S][j];                // 每个新点边权 × 当前深度
                    }
                if (!ok) continue;
                f[dep][S | sub] = min(f[dep][S | sub],
                                      f[dep - 1][S] + w * (dep - 1));
            }
        }

    int ans = 0x3f3f3f3f;
    for (int dep = 1; dep <= n; dep++)
        ans = min(ans, f[dep][(1 << n) - 1]);
    cout << ans << endl;
    return 0;
}

练习

P2622关灯问题 II灯的开关态压成 mask，每个按钮=对若干位做一次翻转（异或）——按一个按钮就是 S ⊕ 按钮mask。求从初始态到全灭的最少按压，状压 + BFS 最短步。在洛谷打开
P3694邦邦的大合唱站队把「已经排成连续块的乐队集合」压成 mask，dp[S]=让 S 中乐队各自连续所需最少移出人数，枚举下一个整块接入的乐队——覆盖式扩展 + 前缀计数。在洛谷打开

已进入 状压 + 覆盖 · 状压 DP · DP大师