题目

问题描述

糖果店的老板一共有 M 种口味的糖果出售。为了方便描述，我们将 M 种口味编号 1 ∼ M。
小明希望能品尝到所有口味的糖果。遗憾的是老板并不单独出售糖果，而是 K 颗一包整包出售。
幸好糖果包装上注明了其中 K 颗糖果的口味，所以小明可以在买之前就知道每包内的糖果口味。
给定 N 包糖果，请你计算小明最少买几包，就可以品尝到所有口味的糖果。

输入

第一行包含三个整数 N、M 和 K。
接下来 N 行每行 K 这整数 T1, T2, · · · , TK，代表一包糖果的口味。

输出

一个整数表示答案。如果小明无法品尝所有口味，输出 −1。

样例输入

6 5 3
1 1 2
1 2 3
1 1 3
2 3 5
5 4 2
5 1 2

样例输出

2

题目分析

一道状压DP，入门级的。题目要求求糖果包数的最小值，又考虑到题目中给出的M范围非常的小，因此想到用状压DP将20维的问题压缩到一维，通过枚举二进制逐位数字来模拟糖果味道的排列组合。
具体做法就是开一个1<<m的数组，通过或运算模拟集合的并操作，枚举每一种糖果味道的排列组合，并根据上一阶段的最优值更新当前阶段的最优值。由于每一包糖果只有选和不选两种情况，因此转移公式也非常简单，就是选上一阶段+1包（选中当前糖果）还是不选当前这一包，不改变当前阶段最优值。注意：没有处理到的排列情况不需要考虑，直接跳过。

AC代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

typedef long long ll;
using namespace std;
const int maxn = 105;
int n, m, k;
int a[maxn];
int dp[1 << 20];

void solve() {
    dp[0] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 1 << m; j++) { //枚举所有糖果种类的排列组合
            if (dp[j] > maxn)
                continue;
            dp[j | a[i]] = min(dp[j | a[i]], dp[j] + 1);
        }
    }
}

int main() {
    int tmp;
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) { //枚举糖果的包数
        for (int j = 0; j < k; j++) { //枚举每一包的k种糖果味道
            cin >> tmp;
            a[i] |= 1 << tmp - 1;//取第tmp位为1
        }
    }
    memset(dp, 127, sizeof(dp));
    solve();
    cout << (dp[(1 << m) - 1] > maxn ? -1 : dp[(1 << m) - 1]) << endl;
    return 0;
}