矩阵消除游戏

题目地址：

https://ac.nowcoder.com/acm/problem/200190

基本思路：

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false); cin.tie(0)
#define int long long
#define ll long long
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF 0x3f3f3f3f

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

const int maxn = 20;
int n,m,k;
int a[maxn][maxn];
int h_sum[maxn],l_sum[maxn],del[maxn];
signed main() {
  IO;
  cin >> n >> m >> k;
  rep(i,0,n-1) rep(j,0,m-1) cin >> a[i][j];
  for(int i = 0 ; i < n ; i++){ // 行前缀和;
    h_sum[i] = 0;
    for(int j = 0 ; j < m ; j++) h_sum[i] += a[i][j];
  }
  for(int j = 0 ; j < m ; j++) { // 列前缀和;
    l_sum[j] = 0;
    for (int i = 0; i < n; i++) l_sum[j] += a[i][j];
  }
  int ans = 0;
  for(int p = 0 ; p < (1 << n) ; p++){ // 枚举行的选择状态;
    int cnt = __builtin_popcount(p); // 选择了的行数;
    if(cnt > k) continue; // 如果大于k,那么不可能;
    int res = 0;
    mset(del,0); // del记录算行时,每列被计算的部分;
    for(int i = 0 ; i < n ; i++) {
      if ((p >> i) & 1) {
        res += h_sum[i]; // 行的权值贡献;
        for (int j = 0; j < m; j++) del[j] += a[i][j];
      }
    }
    vector<int> now;
    for(int j = 0 ; j < m ; j++) {
      now.push_back(l_sum[j] - del[j]); // 现在每列剩余的权值,为整列权值减行中被计算部分;
    }
    sort(all(now),greater<>()); // 从大到小排序,贪心取最多的;
    int z = k - cnt;
    for(int i = 0 ; i < z && i < SZ(now) ; i++) res += now[i];
    ans = max(ans,res);
  }
  cout << ans << '\n';
  return 0;
}