【每日一题】矩阵消除游戏

题目

牛妹在玩一个名为矩阵消除的游戏，矩阵的大小是 $n$ 行 $m$ 列，第 $i$ 行第 $j$ 列的单元格的权值为 $a_{i,j}$ 。
牛妹可以进行 $k$ 个回合的游戏，在每个回合，牛妹可以选择一行或者选择一列，然后将这一行或者这一列的所有单元格中的权值变为 0，同时牛妹的分数会加上这一行或者这一列中的所有单元格的权值的和。
求牛妹的最大得分。

解题思路

如果 $k \ge m$ 或 $k \ge n$ ，那么可以选择矩阵的所有数，直接返回矩阵中数的总和。

使用二进制枚举的方法，枚举所有行的情况： $t$ 的二进制中，如果第 $i$ 位为 0，则表示没有选择第 $i$ 行，否则表示选择了这一行。
如果选中的行数 $rn$ 大于 $k$ ，表示这种情况不存在。
计算选中的所有行的和 $sum$ ，然后将这些行的数据清零，记录在 $mat$ 。
然后直接贪心选择列：计算 $mat$ 中所有列的和，选中 $cn = k-rn$ 个最大的数据列加入 $sum$ 中，更新最大得分 $ans$ 。

不能直接贪心，因为消除的行（列）对列（行）有影响，即每次的选择都会影响到下一次的选择。

C++代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<int>> a(n, vector<int>(m));
    int sum = 0;
    vector<int> sr(n,0);
    for(int i=0; i<n; ++i){
        for(int j=0; j<m; ++j){
            cin >> a[i][j];
            sr[i] += a[i][j];
        }
        sum += sr[i];
    }
    if(k>=n || k>=m){
        cout << sum << endl;
        return 0;
    }
    int ans = 0;
    int status = (1<<n)-1;
    for(int t=0; t<=status; ++t){
        int rn = 0;
        int tmp = t;
        while(tmp){
            if((tmp&1)) ++rn;
            tmp>>=1;
        }
        if(rn>k)
            continue;
        int cn = k - rn;
        sum = 0;
        vector<vector<int>> mat = a;
        for(int i=0; i<n; ++i){
            tmp = 1<<i;
            if((t&tmp)){
                sum += sr[i];
                for(int j=0; j<m; ++j){
                    mat[i][j] = 0;
                }
            }
        }

        vector<int> cs(m,0);
        for(int i=0; i<n; ++i){
            for(int j=0; j<m; ++j){
                cs[j] += mat[i][j];
            }
        }
        sort(cs.rbegin(), cs.rend());
        for(int j=0; j<cn; ++j)
            sum += cs[j];
        ans = max(ans, sum);
    }
    cout << ans << endl;
    return 0;
}