蓝桥杯备考：贪心算法之矩阵消除游戏

这道题是牛客上的一道题，它呢和我们之前的排座位游戏非常之相似，但是，排座位问题选择行和列是不会改变元素的值的，这道题呢每每选一行都会把这行或者这列清零，所以我们的策略就是先用二进制把选择所有行的情况全部枚举出来，接着再选择列，找出和最大的情况即可

怎么用二进制列举情况，比如一共有3行，我们的选择是 000 001 010 011 100 110 111，也就是说到1000结束，也就是把1左移动3就行了

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 20;
int a[N][N];
int n, m, k;
int col[N];
int calc(int x)
{int cnt = 0;while (x){x = x & (x-1);cnt++;}return cnt;}
bool cmp1(int x1, int x2)
{return x1 > x2;
}
int main()
{cin >> n >> m >> k;for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){cin >> a[i][j];}}int ret = 0;for (int i = 0; i < (1<<n); i++){int c = calc(i);if(c > k) continue;int sum = 0;int tmp = i;memset(col, 0, sizeof(col));for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){if ((tmp >> i) & 1) sum += a[i][j];elsecol[j] += a[i][j];}}sort(col, col + m, cmp1);int tmp2 = calc(tmp);for (int i = 0; i < k-tmp2; i++){sum += col[i];}ret = max(ret, sum);}cout << ret << endl;return 0;
}