[蓝桥杯 2019 省 A] 糖果

题意

有 N 包糖果，M 种口味。

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

思路

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

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72#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 \mid pack\_mask[i]] =\min(dp[mask \mid pack\_mask[i]],\ dp[mask]+1)

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

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

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

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44#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(N 2^M)$ ，空间复杂度 $O(2^M)$ 。

总结

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

[蓝桥杯 2019 省 A] 糖果

目录

题意

思路

DP 转移方程

代码

复杂度

总结