矩阵消除游戏代码

由于行的选择会影响列，考虑到数据范围较小，可以考虑枚举思路。

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 20;

int n, m, k;
int a[N][N];
int col[N];

int calc(int n) {
	int ret = 0;
	while(n) {
		n &= n - 1;
		ret++;
	}
	return ret;
}

int main() {
	cin >> n >> m >> k;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			cin >> a[i][j];
		}
	}
	
	int ans = 0;
	for(int st = 0; st <= (1 << n); st++) {
		int cnt = calc(st);
		if(cnt > k) continue;
		
		memset(col, 0, sizeof col);
		int sum = 0;
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= m; j++) {
				if(st >> i - 1 & 1) sum += a[i][j];
				else col[j] += a[i][j];
			}
		}
		
		sort(col + 1, col + m + 1, greater<int>());
		for(int i = 1; i <= min(k - cnt, m); i++) {
			sum += col[i];
		}
		ans = max(ans, sum);
	}
	
	cout << ans << endl;
	return 0;
}