真题解析│蓝桥杯省赛真题之糖果
2019年蓝桥杯软件类省赛（软件类）C/C++大学A组第9题 “糖果”，题目链接：
*本文内容由倪文迪（华东理工大学计算机系软件192班）和罗勇军老师提供。
01
题目描述
糖果店的老板一共有M 种口味的糖果出售。为了方便描述，我们将M种口味编号1~M。
小明希望能品尝到所有口味的糖果。遗憾的是老板并不单独出售糖果，而是K颗一包整包出售。
幸好糖果包装上注明了其中K 颗糖果的口味，所以小明可以在买之前就知道每包内的糖果口味。
给定N 包糖果，请你计算小明最少买几包，就可以品尝到所有口味的糖果。
输入：第一行包含三个整数N、M 和K。
接下来N 行每行K 这整数T1,T2,…,TK，代表一包糖果的口味。
1=N=100，1=M=20，1=K=20，1=Ti=M。
输出：一个整数表示答案。如果小明无法品尝所有口味，输出-1。
02
题解
1
暴力
先想想暴力法：对 n 包糖果做任意组合，找到其中一种组合，能覆盖所有口味，并且需要的糖果包数量最少。n 包糖果的组合共有2 n 种，而n=100，显然会严重超时。
2
状态压缩DP
本题很容易想到用DP来做。
（1）定义状态d p [ i ]，表示得到口味组合 i 所需要的最少糖果包数量。
（2）状态如何转移？往口味组合 i 中加入一包糖果，设得到新的口味组合 j ，说明从 i 到 j 需要糖果包数量d p [ i ] + 1 。若原来的d p [ j ] 大 于 d p [ i ] + 1，说明原来得到 j 的方法不如现在的方法，更新d p [ j ] = d p [ i ] + 1。
这里关键的问题是如何表示口味组合。学过状态压缩DP的队员都知道，像题目中只有小规模的m=20这种应用，用状态压缩的二进制数来表示口味是很简单的。
例如一包里面有3颗糖果，分别是“2，3，5”三种口味，用二进制数“10110”表示，二进制数的每一位表示一种口味。
状态压缩DP的原理和扩展学习，参考文章。
注意文章中这句话：“这样概况状态压缩DP的思想：集合的状态（子集或排列），如果用二进制表示状态，并用二进制的位运算来遍历和操作，又简单又快。当然，由于集合问题是NP问题，所以状态压缩DP的复杂度仍然是指数的，只能用于小规模问题的求解。”
下面给出C++代码，代码中详细解释了状态压缩的表示和DP转移。总复杂度是O ( n2 m )，当n=100，m=20时，循环约1亿次，提交到OJ，勉强AC。
//改写自：User: 20192131006 Time:550 ms Memory:6216 kb
# includebits/stdc++.h
usingnamespacestd;
intdp[ 1 20]; //dp[v]:得到口味为v时需要的最少糖果包数量
intST[ 100]; //ST[i]：第i包糖果的口味
intmain{
intn,m,k; cinnmk;
inttot=( 1m) -1; //tot：二进制是m个1，表示所有m种口味
memset(dp, -1, sizeofdp);
for( inti= 0; in; i++){
intst= 0;
for( intj= 0; jk; j++){
intx;
cinx;
st|=( 1x -1); //状态压缩
dp[st]= 1; //dp[v]:得到口味为v时需要的最少糖果包数量
ST[i]=st; //ST[i]：第i包糖果的口味
for( inti= 0; i=tot; i++) //遍历所有口味组合
if(dp[i]!= -1) //已存在得到口味i的最少糖果包数量
for( intj= 0; jn; j++) { //检查给定的n包糖果
intst=ST[j];
if(dp[i|st]== -1|| dp[i|st]dp[i]+ 1) //状态转移
dp[i|st]=dp[i]+ 1;
cout dp[tot]; //得到所有口味tot的最少糖果包数量
return0;
本来想加上Python代码的，但是众所周知，Python的for循环很慢，本题有1亿次循环，还是算了。
03
参考书籍