P8687 [蓝桥杯 2019 省 A] 糖果

题目描述

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

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

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

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

输入格式

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

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

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

2

说明/提示

对于 $30\mathrm{\%}$ 的评测用例，$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 题。

思路

这是一个状态压缩DP的题目 可以用二进制状态来表示购买糖果的集合，用dp[i][j]表示前i包时，达到状态j所需要的最少包数

题解

#include <bits/stdc++.h>
#define ll long long
#define debug(x) #x << ": " << x << " "

using namespace std;

int dp[1][1 << 20 + 4];
int items[128];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    memset(items, 0, sizeof(int) * 128);
    memset(dp, 0x3f3f3f3f, sizeof(int) * 1 * (1 << 20 + 4));

    int N, M, K;
    cin >> N >> M >> K;
    int a;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 0; j < K; j++)
        {
            cin >> a;
            items[i] |= 1 << (a - 1);
        }
    }
    int sta_max = (1 << M) - 1;
    int now = 0;
    dp[now][0] = 0;
    for (int i = 1; i <= N; i++)
    {
        for (int j = sta_max; j > 0; j--)
        {
            dp[now][j] = min(dp[now][j], dp[now][j & (~items[i])] + 1);
        }
    }
    if (dp[now][sta_max] > N)
    {
        cout << -1;
    }
    else
    {
        cout << dp[now][sta_max];
    }

    return 0;
}