AcWing 1243. 糖果
原题链接
中等
作者:
最后五分钟
,
2024-03-15 19:19:22
,
所有人可见
,
阅读 11
01背包+状态压缩 代码更简洁
#include<bits/stdc++.h>
#define LL long long
#define x first
#define y second
#define de(x) cout<<#x<<" = "<<x<<" "
#define deg(x) cout<<#x<<" = "<<x<<endl
using namespace std;
const int N=110,M=1<<20;
int f[M];
int w[N];
typedef pair<int,int> PII;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,m,k;
cin>>n>>m>>k;
memset(f,0x3f,sizeof f);
for(int i=1;i<=n;i++)
{
for(int j=0;j<k;j++)
{
int x;
cin>>x;
w[i]|=(1<<x-1);
}
}
f[0]=0;
for(int i=1;i<=n;i++)
for(int j=(1<<m)-1;j>=0;j--)
{
f[j]=min(f[j],f[j&~w[i]]+1);
}
if(f[(1<<m)-1]>=0x3f3f3f3f)f[(1<<m)-1]=-1;
cout<<f[(1<<m)-1]<<endl;
return 0;
}