题目描述：
给你一个下标从 0 开始、大小为 m x n 的二进制矩阵 matrix ；另给你一个整数 numSelect，表示你必须从 matrix 中选择的 不同 列的数量。
如果一行中所有的 1 都被你选中的列所覆盖，则认为这一行被 覆盖 了。
形式上，假设 s = {c1, c2, ...., cnumSelect} 是你选择的列的集合。对于矩阵中的某一行 row ，如果满足下述条件，则认为这一行被集合 s 覆盖：
- 对于满足
matrix[row][col] == 1 的每个单元格 matrix[row][col]（0 <= col <= n - 1），col 均存在于 s 中，或者 row 中 不存在 值为 1 的单元格。
你需要从矩阵中选出 numSelect 个列，使集合覆盖的行数最大化。
返回一个整数，表示可以由 numSelect 列构成的集合 覆盖 的 最大行数 。
数据范围：
$1\le m, n \le 12, 1\le numSelect \le n$
题解：
数据范围很小，应该是暴力枚举。
子集型枚举，可以二进制枚举，或者枚举选与不选，或者枚举选哪一列。
二进制枚举，然后使用 __builtin_popcount 统计整数内有多少个 1，等于 $numSelect$ 的可以算一下覆盖行数。
选与不选，记录一下选了多少列了，如果剩余的不够，直接返回剪枝。
选哪一列，每次只能选 $step$ 后面的列，避免重复，同样也记录选了多少列了，如果剩余的不够，直接返回剪枝。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int ans = 0;
vector<bool> vis;
vector<int> status;
int n, m;
void dfs(int step, int selectCnt, int selectStatus, int numSelect)
{
if (selectCnt == numSelect)
{
int tmp = 0;
for (auto &s : status)
{
if ((s | selectStatus) == selectStatus)
{
tmp++;
}
}
ans = max(ans, tmp);
return;
}
if (step >= m)
return;
if (selectCnt + (m - step) < numSelect)
return;
selectStatus |= (1 << step);
dfs(step + 1, selectCnt + 1, selectStatus, numSelect);
selectStatus &= ~(1 << step);
dfs(step + 1, selectCnt, selectStatus, numSelect);
}
int maximumRows(vector<vector<int>> &matrix, int numSelect)
{
n = matrix.size(), m = matrix[0].size();
status.resize(n);
vis.resize(n);
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
if (matrix[i][j])
{
status[i] |= (1 << j);
}
}
}
dfs(0, 0, 0, numSelect);
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int ans = 0;
vector<bool> vis;
vector<int> status;
int n, m;
int maximumRows(vector<vector<int>> &matrix, int numSelect)
{
n = matrix.size(), m = matrix[0].size();
status.resize(n);
vis.resize(n);
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
if (matrix[i][j])
{
status[i] |= (1 << j);
}
}
}
for (int i = 0; i < (1 << m); ++i)
{
if (__builtin_popcount(i) != numSelect)
continue;
int tmp = 0;
for (auto &s : status)
{
if ((s | i) == i)
tmp++;
}
ans = max(ans, tmp);
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int ans = 0;
vector<int> status;
int n, m;
void dfs(int step, int selectCnt, int selectStatus, int numSelect)
{
if (selectCnt == numSelect)
{
int tmp = 0;
for (auto &s : status)
{
if ((s | selectStatus) == selectStatus)
{
tmp++;
}
}
ans = max(ans, tmp);
return;
}
if (selectCnt + (m - step) < numSelect)
return;
for (int i = step; i < m; ++i)
{
dfs(i + 1, selectCnt + 1, selectStatus | (1 << i), numSelect);
}
}
int maximumRows(vector<vector<int>> &matrix, int numSelect)
{
n = matrix.size(), m = matrix[0].size();
status.resize(n, 0);
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
if (matrix[i][j])
{
status[i] |= (1 << j);
}
}
}
dfs(0, 0, 0, numSelect);
return ans;
}
};
|