AcWing 1243. 糖果
原题链接
中等
作者:
ustbweihy
,
2020-09-13 12:04:48
,
所有人可见
,
阅读 1175
//糖果
//大致顺序:先枚举可选择数最少的一列,然后再在这一列中枚举选择哪一行
//这样的时间复杂度应该是最低的,
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
const int N=110, M=1<<20;
vector<int > col[N];//用来记录col中每一列可选择的行数有哪些
int n,m,k;
int log2[M];//预处理,方便计算 log2(2的n次方)
int lowbit(int x)
{
return x& -x;
}
int h(int state)
{
//编写估价函数,看这时的state最少需要用几行来完成
int res=0;
//求最小方案数时,假设选择了某一列,则等价于选择了这一列的全部方案数
for(int i=(1<<m)-1-state;i;i-=lowbit(i))
{
int c=log2[lowbit(i)];//i返回最后一位1,通过log2直接映射为最后一位1的位置
res++;
for(auto row:col[c])
{
i=i&~row; //row表示哪一列有1,每次选择一种方案,等价于将这种方案对应的位变为0,通过&操作实现
}
}
return res;
}
bool dfs(int depth,int state)// depth表示层数,state用于维护选择糖果过程中已经选择了哪些口味
{
if(!depth||h(state)>depth)
{
//若可选择的方案为0或者最小需要选择的方案数都小于当前可选的方案数的话,则判断是否合法
//判断方法:看state是否全为1
return state==(1<<m)-1;// (1<<m)-1表示m位全是一, 即2^m-1
}
//接下来找可选择数最少的一列
int t=-1;//t是指向选择数最少的那一列的指针
//*****
for (int i = (1 << m) - 1 - state; i; i -= lowbit(i))
{
int c = log2[lowbit(i)];
if (t == -1 || col[t].size() > col[c].size())
t = c;
}
//接下来枚举选择哪一行
for(auto row: col[t])
{
if(dfs(depth-1,state|row)) return true;
}
return false;
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
//预处理log2
for(int i=0;i<m;i++)
{
log2[1<<i]=i;
}
for(int i=0;i<n;i++)
{
int state=0;
//将该包糖果所包含的糖果对应的位数置为1
for(int j=0;j<k;j++)
{
int c;
cin>>c;
state=state|1<<c-1;
}
//找出这包糖果 哪个位置可以填成1,将该列对应的col+1
for(int j=0;j<m;j++)
{
if(state>>j&1)//若第j位有1
{
col[j].push_back(state);
}
}
}
int depth=0;
while(!dfs(depth,0)&&depth<=m) depth++;
if(depth>m) depth=-1;
cout<<depth<<endl;
return 0;
}