现在刷点算法题目练练手QAQ
应该还来得及QAQ）
这是一道dp动态规划的问题，洛谷P8687，蓝桥杯 2019 省 A题

糖果问题 (蓝桥杯 2019 省 A)

题目描述

糖果店的老板一共有 M 种口味的糖果出售。为了方便描述，我们将 M 种口味编号 1 ∼ M。

小明希望能品尝到所有口味的糖果。遗憾的是老板并不单独出售糖果，而是 K 颗一包整包出售。

幸好糖果包装上注明了其中 K 颗糖果的口味，所以小明可以在买之前就知道每包内的糖果口味。

给定 N 包糖果，请你计算小明最少买几包，就可以品尝到所有口味的糖果。

输入格式

第一行包含三个整数 N、M 和 K。

接下来 N 行每行 K 这整数 T_1,T_2, \cdots ,T_K，代表一包糖果的口味。

输出格式

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

样例 #1

样例输入 #1

样例输出 #1

提示

对于 30\% 的评测用例，1 \le N \le 20。

对于所有评测样例，1 \le N \le 100，1 \le M \le 20，1 \le K \le 20，1 \le T_i \le M。

蓝桥杯 2019 年省赛 A 组 I 题。

分析

解题思路

考虑到题目中 M 的值较小，可以使用状态压缩动态规划来解决这个问题。我们用一个整数的二进制位来表示糖果的口味是否被选中（即是否买过包含该口味的糖果）。例如，如果有 5 种口味的糖果，二进制数 10110 表示买过包含第 1、2、4 种口味的糖果，但没有买过第 3 和 5 种口味的糖果。

我们定义 dp[i] 表示为了凑齐状态 i 所表示的口味集合，最少需要买的糖果包数量。状态 i 是一个二进制数，它的每个位表示一个口味是否被凑齐。例如，dp[15] 表示凑齐前四种口味最少需要买的糖果包数量。

状态转移

对于每一种可能的状态 i，我们尝试通过添加一个新的糖果包 j 来更新状态。如果当前状态为 i，通过买入第 j 包糖果，我们可以得到一个新的状态 i | v[j]（其中 v[j] 表示第 j 包糖果所包含的口味的状态）。状态转移方程为：

dp[i | v[j]] = min(dp[i | v[j]], dp[i] + 1);

这表示通过当前状态 i，加上第 j 包糖果，可以到达新状态 i | v[j]，并且尝试用更少的包数来更新这个状态。

初始化

所有状态的 dp 值初始化为一个非常大的数（比如 25 或者 0x3f3f3f3f 因为题目最多有 20种包装，使用不可能超过 20），表示最开始所有口味的糖果都未被凑齐。对于每包糖果，我们直接将其能覆盖的口味状态 dp[h] 设置为 1，因为单独一包糖果就可以实现这个状态。dp[0] 初始化为 0，表示没有任何口味的糖果时不需要买糖果。

答案输出

最终，dp[(1 << M) - 1] 即为答案，这表示所有口味都被凑齐的状态。如果这个值没有被更新过（即仍然是初始化的非常大的数），则输出 -1 表示无法凑齐所有口味。

代码实现

#include <bits/stdc++.h>
// 引入所有标准库


using namespace std;

int M, K;
int N;
int n[110], k[22], m[22];
// M、K 和 N 分别表示糖果口味数、每包糖果数和总包数
// n 数组用于以二进制形式存储每包糖果的口味组合
// k 数组是临时存储每包糖果口味的数组
// m 数组用于计算每种口味的出现次数

int dp[1 << 20];
// 动态规划的 dp 数组，使用位操作支持多达20种口味

int main()
{
    scanf("%d%d%d", &N, &M, &K);
    // 读入包数、口味数和每包糖果数

    memset(dp, 25, sizeof(dp));
    // 将 dp 数组初始化为一个较高的值（对于这个上下文来说，可以认为是无限大）

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < K; ++j)
        {
            scanf("%d", &k[j]);
            // 读取当前包中的口味

            ++m[k[j]];
            // 计算每种口味的出现次数

            if ((n[i] & (1 << (k[j] - 1))) == 0)
                n[i] = n[i] | (1 << (k[j] - 1));
            // 将当前包的口味编码成一个二进制数
            // 如果一个口味在 n[i] 中还未被标记，则通过位或操作添加它
        }
        dp[n[i]] = 1; // 标记这种口味组合可以通过1包糖果实现
    }

    // 检查是否能获取所有口味
    for (int i = 1; i <= M; i++)
    {
        if (m[i] == 0)
        {
            // 如果有任何口味未出现过，则不可能获得所有口味
            printf("-1");
            return 0;
        }
    }

    dp[0] = 0; // 基础情况：0种口味需要0包糖果

    // 使用动态规划找到获得所有口味组合所需的最少包数
    for (int i = 0; i < (1 << M); i++)
    {
        for (int j = 0; j < N; ++j)
        {
            dp[i | n[j]] = min(dp[i] + 1, dp[i | n[j]]);
            // 对于每种组合 i，尝试添加一包 j 来达到新的组合
            // 更新 dp 数组为所需最少包数
        }
    }

    printf("%d", dp[(1 << M) - 1]);
    // 打印获得所有口味所需的最少包数
    return 0;
}