AcWing 1243. 糖果
原题链接
中等
作者:
Lauren_9
,
2022-02-23 17:07:17
,
所有人可见
,
阅读 212
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 110, M = 20;
int n, m, k;
int a[N], log2[(1 << M) + 10];
vector<int> col[M];
int lowbit(int x){
return x & -x;
}
int h(int state){
int floor = 0;// 最少需要再选几行,下限
for(int i = (1 << m) - 1 - state; i > 0; i -= lowbit(i)){
int c = log2[lowbit(i)];
floor++;
for(auto row : col[c]){
/*
把row中所有的糖果从i中去掉,i中要选的为1,row中包含的为1
i row out
0 0 0 本来i不需要选,不管row中有没有都不用选
0 1 0
1 0 1 i需要,row中有才能选,选完后i就不需要了
1 1 0
所以 out = i & ~row (m2) = M0 & M1 & M3
*/
// i = i & ~row;
i = (i | row) & (i | ~row) & (~i | ~row);
}
}
return floor;
}
bool dfs(int depth, int state){ // 还需要往下走几层,此时的状态
// if(!depth || depth < h(state) ) return state == (1 << m) - 1;
if(!depth) return state == (1 << m) - 1;
// 找到可选方案数最小的一列
int t = -1;
for(int i = (1 << m) - 1 - state; i > 0; i -= lowbit(i)){
int c = log2[lowbit(i)];
if(t == -1 || col[c].size() < col[t].size())
t = c;
}
// 枚举选择该列的所有方案
for(auto row : col[t]){
if(dfs(depth - 1, state | row))
return true;
}
return false;
}
int main(int argc, char *argv[]) {
cin >> n >> m >> k;
for(int i = 0; i < m; i++) log2[1 << i] = i;
for(int i = 1; i <= n; i++){
for(int j = 0; j < k; j++){
int x;
scanf("%d", &x);
x--;
a[i] |= 1 << x;
}
for(int j = 0; j < m; j++){
if(((a[i] >> j) & 1) == 1)
col[j].push_back(a[i]);
}
}
// 迭代加深
int depth = 0;
while(depth <= m && !dfs(depth, 0) ) depth++;
if(depth > m) depth = -1;
cout << depth << endl;
return 0;
}