T18:糖果

1）题目意思

有 M 种口味（编号 1 到 M）。现在给你 N 包糖果，每包有 K 颗，输入会告诉你这一包里每颗糖的口味（同一包里口味可能重复）。

小明要买一些包，使得买到的所有包里出现过的口味种类能覆盖 1..M 全部口味。

要求输出：

• 最少买几包能覆盖全部口味
• 如果无论怎么买都覆盖不了，输出 -1

范围：N<=100，M<=20，K<=20。

---

2）思路解析（状态压缩 DP）

因为 M<=20，可以用一个二进制 mask 表示“已经覆盖了哪些口味”。

• mask 的第 i 位为 1 表示口味 i+1 已经品尝到
• 目标是得到 FULL = (1<<M)-1

先把每一包糖转换成一个 bagMask：

• 读入这包的 K 个口味 t
• 把对应的位设为 1（重复口味不会影响）

然后做最短步数 DP：

• dp[mask] 表示达到覆盖集合 mask 的最少包数

• 初始：dp[0]=0

• 转移：对每一包 bagMask，从 mask 到 mask | bagMask

  dp[mask | bagMask] = min(dp[mask | bagMask], dp[mask] + 1)

最后看 dp[FULL]：

• 若还是无穷大，输出 -1
• 否则输出它

复杂度：

• 状态数 2^M 最大约 1,048,576
• N 最大 100
• 总体大约 N * 2^M，可以接受（常见做法）

---

3）代码

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

const int INF=1e9;                                       // 定义一个很大的数表示不可达

int main(){                                              // 主函数入口
    ios::sync_with_stdio(false);                         // 加速输入输出
    cin.tie(nullptr);                                    // 加速输入输出

    int N,M,K;                                           // N包，M种口味，每包K颗
    cin>>N>>M>>K;                                        // 读入 N M K

    static int bag[105];                                 // bag[i] 存第i包的口味集合mask
    for(int i=1;i<=N;i++){                               // 枚举每一包
        int mask=0;                                      // 当前包的口味集合初始化为0
        for(int j=1;j<=K;j++){                           // 读入这包的K颗糖
            int t;                                       // t表示口味编号
            cin>>t;                                      // 读入口味
            t--;                                         // 转成0-based，范围0..M-1
            mask|=(1<<t);                                // 把该口味加入集合（重复无影响）
        }
        bag[i]=mask;                                     // 保存该包的mask
    }

    int FULL=(1<<M)-1;                                   // FULL表示全部口味都覆盖的目标mask

    static int dp[1<<20];                                // dp[mask]：覆盖mask所需的最少包数
    for(int mask=0;mask<=FULL;mask++){                   // 初始化dp
        dp[mask]=INF;                                    // 初始都设为不可达
    }
    dp[0]=0;                                             // 什么都不买，覆盖集合为空，包数为0

    for(int i=1;i<=N;i++){                               // 依次考虑每一包（0/1选择）
        int b=bag[i];                                    // 取出第i包的mask
        for(int mask=FULL;mask>=0;mask--){               // 倒序枚举mask，避免一包被用多次
            if(dp[mask]==INF)continue;                   // 当前mask不可达则跳过
            int nmask=mask|b;                            // 买这包后得到的新覆盖集合
            dp[nmask]=min(dp[nmask],dp[mask]+1);         // 更新最少包数
        }
    }

    if(dp[FULL]==INF){                                   // 如果目标状态仍不可达
        cout<<-1<<endl;                                  // 输出-1
    }else{                                               // 否则可达
        cout<<dp[FULL]<<endl;                            // 输出最少包数
    }

    return 0;                                            // 结束程序
}

倒序枚举 mask 的原因是：保证每一包糖最多只被使用一次（0/1 选择）。

1）如果正序枚举会发生什么问题？

假设你正序写：

for(int mask=0;mask<=FULL;mask++){
	dp[mask|b]=min(dp[mask|b],dp[mask]+1);
}

那么当你更新出一个新的状态 mask2 = mask|b 之后，因为是正序，后面循环可能马上又遇到 mask2，又会再用同一包 b 去更新一次，相当于允许：

• 同一包糖被买多次（变成“完全背包”/可重复选）

这就不符合题意（每包只有一包，买不买是 0/1）。

2）倒序为什么能避免重复使用？

倒序写：

for(int mask=FULL;mask>=0;mask--){
	dp[mask|b]=min(dp[mask|b],dp[mask]+1);
}

因为你从大到小扫：

• 当你用 dp[mask] 去更新 dp[mask|b] 时，mask|b 一定 大于等于 mask
• 而倒序遍历时，mask|b 对应的位置已经在前面（更大）遍历过了，不会再被当作“本轮的来源状态”继续往后更新
• 所以这一轮（处理这一包）里，每个状态最多只会“用这包一次”，符合 0/1 选择

3）一句话总结

• 正序：会把同一包当成“可以买无限次”（错误）
• 倒序：保证同一包只用一次（正确）