先上题目蓝桥杯省赛真题题目描述糖果店老板一共有 M 种口味的糖果编号 1∼M。小明想要尝遍全部口味。糖果不单独售卖只能 K 颗一包整包购买。每包糖果的口味已知。给定 N 包糖果求小明最少买几包就能集齐所有 M 种口味。如果无论买多少包都无法集齐所有口味输出 −1。输入描述第一行三个整数 N, M, K。接下来 N 行每行 K 个整数表示一包糖果里的口味。数据范围1 ≤ N ≤ 1001 ≤ M ≤ 201 ≤ K ≤ 20输出描述输出一个整数表示最少购买包数。无解输出 −1。问题分析这道题是最典型、最标准的状态压缩动态规划状压 DP题目。看到M ≤ 20这个关键数据范围就应该立刻想到用二进制表示状态。核心思路用二进制数表示口味集合M ≤ 20一个 int 类型32 位足够存下所有口味的拥有情况。例如 M3拥有口味 1 → 二进制001→ 数字 1拥有口味 13 → 二进制101→ 数字 5拥有全部口味 → 二进制111→ 数字 7即(1M)-1把每包糖果转成一个二进制掩码每包糖果包含哪些口味直接转成一个二进制数。比如一包糖果有口味 2、3 → 掩码110→ 6。DP 状态定义dp[mask]表示获得mask这个口味集合最少需要买几包糖。初始化dp[0] 0一包不买口味为 0数量是 0其余状态初始化为一个很大的数表示暂时无法到达状态转移遍历每一包糖果用它去更新所有可能的状态新状态 旧状态 | 糖果掩码dp[new_mask] min(dp[new_mask], dp[old_mask] 1)答案最终答案就是dp[(1M)-1]如果还是很大说明无解输出 −1。代码演示C#include iostream #include algorithm #include cstring using namespace std; const int INF 0x3f3f3f3f; int dp[1 20]; // 最多 2^20 个状态 int mask[105]; // 每包糖对应的二进制掩码 int main() { int N, M, K; cin N M K; // 把每包糖转成二进制掩码 for (int i 0; i N; i) { int msk 0; for (int j 0; j K; j) { int t; cin t; t--; // 口味转成 0~M-1方便位运算 msk | (1 t); } mask[i] msk; } // DP 初始化 memset(dp, 0x3f, sizeof(dp)); dp[0] 0; // 状态转移 for (int i 0; i N; i) // 枚举每一包糖 { int msk mask[i]; // 逆序遍历防止重复选同一包 for (int j (1 M) - 1; j 0; j--) { if (dp[j] ! INF) { int to j | msk; dp[to] min(dp[to], dp[j] 1); } } } int full (1 M) - 1; if (dp[full] INF) cout -1 endl; else cout dp[full] endl; return 0; }pythondef main(): import sys input sys.stdin.read data input().split() idx 0 N int(data[idx]) idx 1 M int(data[idx]) idx 1 K int(data[idx]) idx 1 masks [] for _ in range(N): msk 0 for __ in range(K): t int(data[idx]) - 1 idx 1 msk | 1 t masks.append(msk) INF float(inf) size 1 M dp [INF] * size dp[0] 0 for msk in masks: # 逆序遍历 for j in range(size-1, -1, -1): if dp[j] ! INF: to j | msk if dp[to] dp[j] 1: dp[to] dp[j] 1 full (1 M) - 1 print(dp[full] if dp[full] ! INF else -1)算法详解1. 状态压缩原理M ≤ 20用一个整数表示拥有的口味集合。第 i 位为 1 → 拥有第 i1 种口味按位或|操作 → 合并两包糖果的口味最终目标(1M)-1→ 所有位都是 1代表集齐所有口味2. DP 初始化dp[0] 0初始状态一包没买口味为空其余设为无穷大表示暂时无法到达该状态3. 为什么要逆序遍历状态逆序遍历可以保证每一包糖果最多只选一次避免重复购买同一包导致答案错误。这是 01 背包思想在状压 DP 里的直接应用。4. 转移方程dp[new_mask] min(dp[new_mask], dp[old_mask] 1)含义买了当前这包糖后新状态的最少包数 原来的包数 15. 时间复杂度总状态数220≈100 万枚举 N100 包总计算量100×100 万 1 亿C 和 Python 都能轻松通过。结语《糖果》是蓝桥杯状压 DP 最经典的入门题也是 01 背包思想与二进制状态压缩的完美结合。