矩阵消除游戏

矩阵消除游戏

思路

直接进行二进制枚举我们要选定的行，然后再贪心地选了，列，这样我们即可以保证我们都选择是最优的，然后取这些选择值里面的最优值就🆗了，具体看代码注释吗。

代码

#include <bits/stdc++.h>

using namespace std;

#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
typedef long long ll;

ll a[20][20];
int n, m, k;

vector<ll> add;

int judge(int x) {
    int sum = 0;
    while(x) {
        if(x & 1)   sum++;
        x >>= 1;
    }
    return sum;
}

int main() {
    // freopen("in.txt", "r", stdin);
    IOS;
    ll s = 0;
    cin >> n >> m >> k;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            cin >> a[i][j], s += a[i][j];
    if(k >= n || k >= m) {
        cout << s << endl;
        return 0;
    }
    ll ans = 0;
    for(int i = 0; i < (1 << n); i++) {//枚举行，
        int num = judge(i);
        if(num > k || k - num > m)  continue;
        ll sum = 0;
        for(int j = 0; j < n; j++) {
            if(((i >> j) & 1) == 0) continue;//没挑选的行跳过，
            for(int l = 0; l < m; l++)
                sum += a[j][l];
        }
        // cout << 1 << endl;
        add.clear();
        for(int j = 0; j < m; j++) {//得到每列剩下的值，
            ll all = 0;
            for(int l = 0; l < n; l++)
                if((i >> l) & 1)    continue;//这列中的元素在行中被挑选过，
                else all += a[l][j];
            add.push_back(all);
        }
        // cout << 1 << endl;
        sort(add.begin(), add.end(), greater<ll> ());
        for(int j = 0; j < k - num && j < m; j++)
            sum += add[j];
        ans = max(ans, sum);
    }
    cout << ans << "\n";
    return 0;
}