糖果（重复覆盖问题）
题意
思路
可以转化为简单的重复覆盖问题，我们用简单的状态压缩写
代码
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
using namespace std
;
typedef long long ll
;
typedef unsigned long long ull
;
#define mst(s,_s) memset(s, _s, sizeof(s))
const double PI
= acos(-1.0);
const double eps
= 1e-6;
const int INF
= 0x3f3f3f3f;
const int N
= 1<<22;
int T
,n
,m
,k
;
ll apple
[N
];
ll f
[N
];
int main() {
cin
>>n
>>m
>>k
;
for(int i
=0;i
<n
;i
++)
{
ll state
=0;
for(int i
=0;i
<k
;i
++){
int a
;
cin
>>a
;
a
--;
state
|=1<<a
;
}
apple
[i
]=state
;
}
for(int i
=0;i
<N
;i
++) f
[i
]=0x3f3f3f3f;
f
[0]=0;
for(int state
=0;state
+1<1<<m
;state
++)
{
int x
=0;
for(int i
=0;i
<m
;i
++)
{
if(!(state
>>i
&1))
{
x
=i
;
break;
}
}
for(int j
=0;j
<n
;j
++)
{
if((apple
[j
]>>x
&1))
{
f
[state
|apple
[j
]] = min(f
[state
|apple
[j
]] , f
[state
]+1);
}
}
}
ll n
=1<<m
;
if(f
[n
-1]==0x3f3f3f3f) cout
<<-1<<endl
;
else
cout
<<f
[n
-1]<<endl
;
return 0;
}
