本文共 1935 字，大约阅读时间需要 6 分钟。

为了解决这个问题，我们需要找到小明最少需要购买多少包糖果，才能品尝到所有 M 种口味。每包糖果包含 K 颗糖果，并且每颗糖果的口味已知。我们将使用动态规划和广度优先搜索（BFS）的方法来解决这个问题。

方法思路

解决代码

#include 
   
    
#include 
    
     
#include 
     
      
using namespace std;
int main() {
    int N, M, K;
    cin >> N >> M >> K;
    vector
      
        w_masks;
    for (int i = 0; i < N; ++i) {
        vector
       
         t_list;
        for (int j = 0; j < K; ++j) {
            int t;
            cin >> t;
            t_list.push_back(t);
        }
        int mask = 0;
        for (int t : t_list) {
            mask |= 1 << (t - 1);
        }
        // 去重处理
        vector
        
          unique_t; for (int t : t_list) { if (!unique_t.empty() && unique_t.back() == t) continue; unique_t.push_back(t); } for (int t : unique_t) { mask |= 1 << (t - 1); } w_masks.push_back(mask); } vector
         
           dp(1 << M, -1); dp[0] = 0; vector
          
            is_processed(1 << M, false); queue
           
             q; q.push(0); is_processed[0] = true; while (!q.empty()) { int mask = q.front(); q.pop(); if (mask == (1 << M) - 1) { return dp[mask]; } for (int w_mask : w_masks) { int new_mask = mask | w_mask; if (dp[new_mask] == -1) { dp[new_mask] = dp[mask] + 1; if (!is_processed[new_mask]) { is_processed[new_mask] = true; q.push(new_mask); } } } } return -1; }
           
          
         
        
       
      
     
    
   

代码解释

• 读取输入：读取 N 包糖果的信息，每包包含 K 颗糖果。
• 生成掩码：将每包的口味转化为掩码，去重后存入 w_masks 数组。
• 初始化状态：dp[0] 初始化为 0，表示初始状态（没有收集任何口味）。
• BFS 处理：使用队列处理每个状态，计算新的状态，并更新 dp 数组。
• 终止条件：一旦找到覆盖所有口味的状态，返回当前包数；否则，返回 -1。

这个方法确保了我们能找到最少的包数，使得小明可以品尝到所有口味，或者判断无法实现的情况。