状态压缩--动态规划

o-Sakurajimamai-o / 2023-09-02 / 原文

状态压缩也就是把多个状态都转译成一个状态,由于题目的题意就是需要一步一步递推也就是dp,但是常规的dp只能计算一个状态,无法满足多个状态,所以可以使用状态压缩.

将这多个状态划分为二进制形式:设有$m$个状态,那么所有的可能状态为 $2^m$ ,如果有4个状态,$0010$ 表示只满足了第二个状态,依次类推

但是可以看出,输出的不可能存在一个都不满足的状态,所以计算时状态总数为 $2^m-1$

状态合并: 使用 $ | $,将两个状态的1合并

题目描述

糖果店的老板一共有 $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
```

把输出的每个包装里面都计算出所含的糖果状态,然后进行dp即可,时间复杂度 $O(n*2^m)$

#include<bits/stdc++.h>
using namespace std;
const int N=500;
int n,m,k;
int f[1<<25],candy[1<<25];
bool vis[1<<25];
int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        int num=0;
        for(int j=1;j<=k;j++){
            cin>>num;
            candy[i]=candy[i]|1<<(num-1);
            vis[candy[i]]=true,f[candy[i]]=1;
        }
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<1<<(m+1);j++)
             if(vis[j]){
                if(!vis[j|candy[i]]) f[j|candy[i]]=f[j]+1;
                else f[j|candy[i]]=min(f[j|candy[i]],f[j]+1);
                vis[j|candy[i]]=true;
             }
    if(!vis[(1<<m)-1]) cout<<-1;
    else cout<<f[(1<<m)-1]<<endl;
    return 0;
}