题解 | #矩阵消除游戏#

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;

int a[20][20];
int lie[20];
int n, m, k;
int calc(int st) {
    int i = 0, cnt = 0;
    int sum = 0;
    while (i<n) {
        if (((st>>i)&1)==1) {
            for (int j=0;j<m;j++) {
                sum += a[i][j];
            }
            cnt++;
        } else {
            for (int j=0;j<m;j++) {
                lie[j] += a[i][j];
            }
        }
        i++;
    }
    if (cnt>k) {
        return 0;
    }
    sort(lie, lie+m,greater<>());
    for (int j=0;j<k-cnt;j++) {
        sum += lie[j];
    }
    return sum;
}

int main() {
    IOS;
    int sum = 0;
    cin>>n>>m>>k;
    for (int i=0;i<n;i++) {
        for (int j=0;j<m;j++) {
            cin>>a[i][j];
            sum += a[i][j];
        }
    }
    if (k>=m||k>=n) {
        cout<<sum;
        return 0;
    }
    int ans = 0;
    //以二进制枚举横
    for (int st=0;st<=((1<<n)-1);st++) {
        memset(lie, 0, sizeof(lie));
        int sum = calc(st);
        ans = max(ans, sum);
    }
    cout<<ans;
    
    return 0;
}