藍橋杯真題——糖果(狀壓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 <bits/stdc++.h>
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";
}