[蓝桥杯 2019 省 A] 糖果

GitHub跳转原题关系图返回列表

把每包糖果压成一个口味集合 mask，设 dp[mask] 为覆盖这些口味所需的最少包数，做集合覆盖型状压 DP。

OJ: luogu

题目 ID: P8687

难度:普及

标签:状态压缩动态规划集合覆盖位运算

创建: 2026-06-21 05:09

更新: 2026-08-09 06:46

后置题目
roj 20011厨师的福报A 教的“围绕已覆盖口味而不是选哪些包设计状态、用位或合并掩码”被 B 原样搬到“不记录选了哪些人，改记录菜的覆盖情况”（代码里就是 a | mask），B 只是在此之上叠加覆盖数封顶到 2 与双 bitmask 的 0/1 背包流程。roj 3003最短Hamilton路径A 教的「把元素集合压成二进制整数 mask、用位表示已覆盖哪些口味」是 B 状压状态的核心一步：B 直接沿用为 f(s,j) 的集合维度，只在其上叠加「最后停在哪个点」维度与边权代价。roj 1221分成互质组A 教的「不围绕选哪些包、而围绕已覆盖集合设计状态，dp[mask]=覆盖该集合的最少数量」被 B 直接继承：B 明确写出把「分组方案」的枚举换成「集合覆盖」的枚举，代码里 f[S]=1+min f[S\T] 就是同一状态设计，只是在其上叠加冲突图/独立集建模与 t=(t-1)&S 的子集枚举。luogu P1294高手去散步B 沿用 A 教的「把已处理的集合压成二进制 mask、用按位或把新元素并入集合」这一步，把覆盖口味换成已访问点并加一维当前终点，由集合覆盖最少包数变成最长简单路径。luogu P1433吃奶酪B 的状压 DP 逐字复用了 A 教的「把元素压成二进制 mask、用 mask|新元素 累积已选集合」这一步：A 用它做集合覆盖 dp[mask]，B 沿用同一累积方式并叠加「最后停在哪块」维度与距离代价，形成台阶式加难。

目录

  1. 题意
  2. 思路
    1. 代码
    2. 复杂度
    3. 总结

    题意

    有 N 包糖果，M 种口味。

    每包糖果里有若干颗糖，给出了这些糖的口味。 要求最少买几包，才能覆盖全部 M 种口味。

    思路

    先看一个只适合小数据验证的暴力：

    cpp
    #include <bits/stdc++.h>
using namespace std;

int n, m, k;
int pack_mask[105];
int choose_pack[105]; // choose_pack[i] = 0/1，表示第 i 包糖果不买/买
int full_mask;
int ans;

int calc_mask() {
    int mask = 0;
    for (int i = 1; i <= n; i++) {
        if (choose_pack[i] == 1) mask |= pack_mask[i];
    }
    return mask;
}

int calc_used() {
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (choose_pack[i] == 1) cnt++;
    }
    return cnt;
}

bool check() {
    return calc_mask() == full_mask;
}

void dfs_choose(int dep) {
    if (dep == n + 1) {
        if (check()) {
            int value = calc_used();
            if (ans > value) ans = value;
        }
        return;
    }

    // 第 dep 包糖果的 01 选择：0 不买，1 买。
    for (int i = 0; i <= 1; i++) {
        choose_pack[dep] = i;
        dfs_choose(dep + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // brute.cpp：枚举买哪些包糖果，统计能否覆盖所有口味。
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        int mask = 0;
        for (int j = 1; j <= k; j++) {
            int x;
            cin >> x;
            mask |= 1 << (x - 1);
        }
        pack_mask[i] = mask;
    }

    full_mask = (1 << m) - 1;
    ans = n + 1;
    dfs_choose(1);

    if (ans == n + 1) {
        cout << -1 << '\n';
    } else {
        cout << ans << '\n';
    }
    return 0;
}

    brute.cpp 把每包糖果看成一个 01 选择：choose_pack[i] = 0/1 表示不买或买。递归先生成完整选择，叶子节点再检查这些包的并集能不能覆盖全部口味，并统计最少购买数量。

    正解的关键是：虽然糖果包数 N 不小，但口味数 M<=20 很小。

    所以不要围绕“选哪些包”设计状态，而要围绕“已经覆盖了哪些口味”设计状态。

    把每包糖果压成一个二进制集合：

    • 第 i 位为 1 表示已经覆盖了第 i 种口味

    设：

    • dp[mask] 表示覆盖到 mask 这些口味时，最少需要买多少包

    如果当前考虑一包糖果 pack_mask，那么就有转移：

    mask -> mask | pack_mask

    DP 转移方程

    买第 i 包糖果时，设这一包覆盖的口味集合为 pack_mask[i]：

    dp[mask∣pack_mask[i]]=min⁡(dp[mask∣pack_mask[i]], dp[mask]+1) dp[mask \mid pack\_mask[i]] =\min(dp[mask \mid pack\_mask[i]],\ dp[mask]+1)

    初始状态是 dp[0]=0，答案是 dp[(1<<M)-1]。

    因为买下这包之后，口味集合只会做一个按位或。

    这就是一个很标准的集合覆盖型状压 DP。

    代码

    cpp
    #include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

int n, m, k;
int pack_mask[105];
int dp[1 << 20];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        int mask = 0;
        for (int j = 1; j <= k; j++) {
            int x;
            cin >> x;
            mask |= 1 << (x - 1);
        }
        pack_mask[i] = mask;
    }

    int full = (1 << m) - 1;
    for (int i = 0; i <= full; i++) {
        dp[i] = INF;
    }
    dp[0] = 0;

    for (int i = 1; i <= n; i++) {
        for (int mask = full; mask >= 0; mask--) {
            int nxt = mask | pack_mask[i];
            dp[nxt] = min(dp[nxt], dp[mask] + 1);
        }
    }

    if (dp[full] >= INF) {
        cout << -1 << '\n';
    } else {
        cout << dp[full] << '\n';
    }
    return 0;
}

    复杂度

    时间复杂度 O(N2M)O(N 2^M)，空间复杂度 O(2M)O(2^M)。

    总结

    这题的核心是盯住真正小的量：不是 N，而是 M。 一旦识别出这一点，题目就会自然转成状压 DP。