1243. 糖果/状态压缩dp【AcWing】

1243. 糖果

糖果店的老板一共有 M种口味的糖果出售。

为了方便描述，我们将 M种口味编号 1∼M。

小明希望能品尝到所有口味的糖果。

遗憾的是老板并不单独出售糖果，而是 K颗一包整包出售。

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

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

输入格式
第一行包含三个整数 N,M,K。

接下来 N行每行 K个整数 T1,T2,⋅⋅⋅,TK，代表一包糖果的口味。

输出格式
一个整数表示答案。

如果小明无法品尝所有口味，输出 −1。

数据范围
1≤N≤100,
1≤M,K≤20,
1≤Ti≤M

输入样例：
6 5 3
1 1 2
1 2 3
1 1 3
2 3 5
5 4 2
5 1 2

输出样例：
2

状态压缩dp

状态压缩dp用位运算实现。
思路：
dp[ i ][ j ]表示前 i 袋糖果集齐 j 种糖果所需要的最少袋数。
可以选择第 i 袋或者不选择第 i 袋。
状态转移方程为：
dp[ i ][ j ]=min( dp[ i - 1 ][ j ] , dp[ i - 1 ][ j & (~ w[ i ])]+1 )
前面那个是不选择第 i 袋，比较好理解，后面那个可以举个例子
例如我们想要 j 为11011，而w[ i ]为 11100，取反后为00011,11011 & 00011 = 10000，故是从10000这个状态转移过来的。
然后要先预处理dp数组为100，dp[0]=0就可以了。

#include<bits/stdc++.h>
using namespace std;
int w[100],dp[1<<20];
int main()
{int n,m,k;cin>>n>>m>>k;int s=(1<<m)-1;for(int i=1;i<=n;i++){for(int j=1;j<=k;j++){int r;cin>>r;w[i]|=1<<r-1;}}for(int i=1;i<(1<<m);i++) dp[i]=100;dp[0]=0;for(int i=1;i<=n;i++){for(int j=(1<<m)-1;j>0;j--){dp[j]=min(dp[j],dp[j&(~w[i])]+1);}}(dp[s]==100)?(cout<<-1<<endl):(cout<<dp[s]<<endl);return 0;
}