solution.cpp

#include <bits/stdc++.h>
using namespace std;
int dp[1 << 20]; //dp[v]表示口味为v时所需要的最少糖果包数
int ST[100];     //100包糖果
int main()
{
    int n, m, k;
    cin >> n >> m >> k;         //输入n包糖果，m个口味，每包k个口味
    int tot = (1 << m) - 1;     //表示所有m种口味各种组合方式
    memset(dp, -1, sizeof dp);  //初始化dp全部为-1
    for (int i = 0; i < n; i++) //依次处理n包糖果
    {
        int st = 0;
        for (int j = 0; j < k; j++) //依次处理每颗糖果口味
        {
            int x;
            cin >> x;
            st |= (1 << x - 1); //把第i包的第j颗糖果加入该包的口味st中
        }
        dp[st] = 1;
        ST[i] = st;
    }
    for (int i = 0; i <= tot; i++) //遍历所有口味组合方式
    {
        if (dp[i] != -1) //表示已存在得到该口味的最少糖果包数量
        {
            for (int j = 0; j < n; j++) //检查给定的n包糖果
            {
                int st = ST[j];
                if (dp[i | st] == -1 || dp[i | st] > dp[i] + 1) //状态转移
                    dp[i | st] = dp[i] + 1;
            }
        }
    }
    cout << dp[tot]; //得到所有口味tot的最少糖果包数
    return 0;
}