蓝桥杯真题——糖果(状压dp板子题)

题目描述

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

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

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

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

输入描述

第一行包含三个整数 N,M,K

接下来 N 行每行 K 这整数 T_1,T_2,··· ,T_KT1​,T2​,⋅⋅⋅,TK​，代表一包糖果的口味。

其中，1≤N≤100,1≤M≤20,1≤K≤20,1≤Ti​≤M。

输出描述

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

输入输出样例

示例

输入

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

输出

2

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

题解：典型的dp板子题，看注释！

#include 
using namespace std;
typedef long long ll;
int dp[1 << 20];
int a[105];
int main()
{
    int n, m, k;
    cin >> n >> m >> k;
    int x;
    for (int i = 0; i < n; i++){
        int t = 0;
        for (int j = 0; j < k; j++){
            cin >> x;
            t |= (1 << (x - 1));
        }
        dp[t] = 1;
        a[i] = t;//把已存在的存储起来以便下面的循环来搜索，很妙！
    }
    int q = (1 << m) - 1;
    for (int i = 1; i <= q;i++){
        if(dp[i]){
            for (int j = 0; j < n;j++){
                if(dp[i|a[j]]==0||(dp[i|a[j]]>(dp[i]+1))){//这两行就是整个代码精髓，一定不会遗漏（dp[i]里的i从小到大+，更新的值一定在后面！）
                    dp[i|a[j]]=dp[i]+1;//更新值！！！ （dp[i]已存在）这两行是说如果i和a[j]的状态叠加不存在，就dp[i]+1,or存在但不是最小值就更新为最小值
                }
            }
        }
    }
    if(dp[q])
    cout << dp[q];
    else
        cout << "-1";
}