附上链接：[蓝桥杯 2019 省 A] 糖果 - 洛谷，有兴趣的小伙伴可以去试试哦~
# [蓝桥杯 2019 省 A] 糖果
## 题目描述
糖果店的老板一共有 $M$ 种口味的糖果出售。为了方便描述，我们将 $M$ 种口味编号 $1$ ∼ $M$。
小明希望能品尝到所有口味的糖果。遗憾的是老板并不单独出售糖果，而是 $K$ 颗一包整包出售。
幸好糖果包装上注明了其中 $K$ 颗糖果的口味，所以小明可以在买之前就知道每包内的糖果口味。
给定 $N$ 包糖果，请你计算小明最少买几包，就可以品尝到所有口味的糖果。
## 输入格式
第一行包含三个整数 $N$、$M$ 和 $K$。
接下来 $N$ 行每行 $K$ 这整数 $T_1,T_2, \cdots ,T_K$，代表一包糖果的口味。
## 输出格式
一个整数表示答案。如果小明无法品尝所有口味，输出 $-1$。
## 样例 #1
### 样例输入 #1
```
6 5 3
1 1 2
1 2 3
1 1 3
2 3 5
5 4 2
5 1 2
```
### 样例输出 #1
```
2
```
题解代码：
#include <bits/stdc++.h>
using namespace std;
#define N 100010
#define ll long long
int main()
{
int n, m, k;
cin >> n >> m >> k;
vector<int> candy(n);
vector<int> f(1 << m, N);
for (int i = 0; i < n; ++i)
{
int sum = 0;
for (int j = 0; j < k; ++j)
{
int temp;
cin >> temp;
sum = sum | 1 << (temp - 1);
}
candy[i] = sum;
}
f[0] = 0;
for (int i = 0; i < 1 << m; ++i)
{
for (int j = 0; j < n; ++j)
{
f[candy[j] | i] = min(f[candy[j] | i], f[i] + 1);
}
}
f[(1 << m) - 1] = f[(1 << m) - 1] == N ? -1 : f[(1 << m) - 1];
cout << f[(1 << m) - 1];
return 0;
}
题解的主要思路：
本题主要用动态规划+状态压缩去做；假设我们有1-N号的糖果，那么我们可以想象成一个N位二进制串，其中第i位为1表示有i号糖果，为0则表示没有，那么我们可以通过这样一个二进制串来表示状态（即所拥有的糖果状态）；
因此对于每包糖果，维护数组candy，将每包糖果进行或操作，得到每包糖果的一个状态；然后创建一个大小为（1<<m）-1的数组f记录某状态所需要的最小糖果包数，然后就可以进行循环求解；
双重循环中外循环是状态，内循环是N包糖果，意思是对于每一种状态，我都拿N包糖果去进行或(也就是我都拿进来一包糖果试试看这个状态会不会更新)，由此来更新状态，这里有一点贪心的思想，最后输出f[(1<<m)-1]，这个状态转化成二进制是全1，也就是我们最终要求的状态啦！
本题的收获：
本题主要的收获还是学会状态压缩和动态规划，了解如何将目前掌握的糖果的状态压缩成一个数，可以通过二进制去表示这个数，再通过或操作去更新状态，由此进行DP（动态规划）
标签：状态,int,题解,candy,蓝桥,##,2019,口味,糖果 From： https://blog.csdn.net/qq_73848829/article/details/141674555