2021年寒假每日一題，2017~2019年的省賽真題，本文內容由倪文迪（華東理工大學計算機系軟體192班）和羅勇軍老師提供，每日一題，關注藍橋杯專欄: https://blog.csdn.net/weixin_43914593/category_10721247.html

2019省賽A組第9題“糖果” ，題目鏈接：
http://oj.ecustacm.cn/problem.php?id=1460

1、題目描述

糖果店的老板一共有M 種口味的糖果出售，為了方便描述，我們將M種口味編號1~M，
小明希望能品嘗到所有口味的糖果，遺憾的是老板并不單獨出售糖果，而是K顆一包整包出售，
幸好糖果包裝上注明了其中K 顆糖果的口味，所以小明可以在買之前就知道每包內的糖果口味，
給定N 包糖果，請你計算小明最少買幾包，就可以品嘗到所有口味的糖果，
輸入：第一行包含三個整數N、M 和K，
接下來N 行每行K 這整數T1,T2,…,TK，代表一包糖果的口味，
1<=N<=100，1<=M<=20，1<=K<=20，1<=Ti<=M，
輸出：一個整數表示答案，如果小明無法品嘗所有口味，輸出-1，

2、題解

2.1 暴力

??先想想暴力法：對 n n n包糖果做任意組合，找到其中一種組合，能覆寫所有口味，并且需要的糖果包數量最少， n n n包糖果的組合共有 2 n 2^n 2n種，而 n n n=100，顯然會嚴重超時，

2.2 狀態壓縮DP

??本題很容易想到用DP來做，
??（1）定義狀態 d p [ i ] dp[i] dp[i]，表示得到口味組合 i i i所需要的最少糖果包數量，
??（2）狀態如何轉移？往口味組合 i i i中加入一包糖果，設得到新的口味組合 j j j，說明從 i i i到 j j j需要糖果包數量 d p [ i ] + 1 dp[i]+1 dp[i]+1，若原來的 d p [ j ] 大 于 d p [ i ] + 1 dp[j]大于dp[i]+1 dp[j]大于dp[i]+1，說明原來得到 j j j的方法不如現在的方法，更新 d p [ j ] = d p [ i ] + 1 dp[j]=dp[i]+1 dp[j]=dp[i]+1，
??這里關鍵的問題是如何表示口味組合，學過狀態壓縮DP的隊員都知道，像題目中只有小規模的m=20這種應用，用狀態壓縮的二進制數來表示口味是很簡單的，
??例如一包里面有3顆糖果，分別是“2，3，5”三種口味，用二進制數“10110”表示，二進制數的每一位表示一種口味，
??狀態壓縮DP的原理和擴展學習，參考博文https://blog.csdn.net/weixin_43914593/article/details/106432695
??注意博文中這句話：“這樣概況狀態壓縮DP的思想：集合的狀態（子集或排列），如果用二進制表示狀態，并用二進制的位運算來遍歷和操作，又簡單又快，當然，由于集合問題是NP問題，所以狀態壓縮DP的復雜度仍然是指數的，只能用于小規模問題的求解，”
??下面給出C++代碼，代碼中詳細解釋了狀態壓縮的表示和DP轉移，總復雜度是 O ( n 2 m ) O(n2^m) O(n2m)，當n=100，m=20時，回圈約1億次，提交到OJ，勉強AC，

//改寫自：User: 20192131006  Time:550 ms  Memory:6216 kb
#include<bits/stdc++.h>
using namespace std;
int dp[1<<20]; //dp[v]:得到口味為v時需要的最少糖果包數量
int ST[100];   //ST[i]：第i包糖果的口味

int main() {
    int n,m,k; cin>>n>>m>>k;

    int tot=(1<<m)-1;  //tot：二進制是m個1，表示所有m種口味

    memset(dp, -1, sizeof dp);

    for (int i=0; i<n; i++){
        int st=0;
        for (int j=0; j<k; j++){
            int x;
            cin>>x;
            st|=(1<<x-1);  //狀態壓縮
        }
        dp[st]=1;   //dp[v]:得到口味為v時需要的最少糖果包數量
        ST[i]=st;   //ST[i]：第i包糖果的口味
    }
    for (int i=0; i<=tot; i++)  //遍歷所有口味組合
        if (dp[i]!=-1)          //已存在得到口味i的最少糖果包數量
            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;
}

??本來想加上Python代碼的，但是總所周知，Python的for回圈很慢，本題有1億次回圈，還是算了，