题解 | #矩阵消除游戏#

• 题目考点：01串枚举+贪心
• 题目大意：从n*m的矩阵中进行k次选择，每次选择一整行或者一整列，得到这一行/列的和，每次选择过后，该行数字将会被消除；求k次选择能得到的最大和。
• 题目分析：初步分析似乎是贪心，每次取最大和的一行或一列，但是很快能想出反例：

举一个反例：
3 4 2
0    0     0    100
100  0     0    100 
10   10    10   0

如上例，若按贪心选第二行+第四列得到300，不如选择第一、四列得310； 一番分析后，我们可以由n、m小于等于15想出，先按01串枚举选行，再对列进行贪心，这样保证不遗漏所有情况，对每一行选或不选进行枚举，算法复杂度2^n，n在15以内，复杂度完全ok

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

using namespace std;
typedef long long LL;

const int N = 20;
int a[N][N], n, m, k, tot;
int b[N][N], col[N];
int cnt, ans;

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

int main()
{
    scanf("%d%d%d", &n, &m, &k);

    for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++)
        scanf("%d", &a[i][j]),
        a[i][m+1] += a[i][j],
        a[n+1][j] += a[i][j],
        tot += a[i][j];

    if(k >= min(m, n))
    {
        printf("%d", tot);
        return 0;
    }

    // 01串枚举
    for(int i = 0; i < (1 << n); i++)
    {
        memcpy(b, a, sizeof a);
        int cnt1 = cnt_1_in_i(i);
        if(cnt1 > k)continue;
        cnt1 = k - cnt1;

        cnt = 0;

        //  枚举选行
        for(int j = 1; j <= n; j++)
        {
            if(i & (1<<(j-1)))
            {
                // 1、加上改行和
                cnt += b[j][m+1];
                // 2、每一行数字所在列减去该数字
                for(int ex = 1; ex <= m; ex++)
                    b[n+1][ex] -= b[j][ex];
            }
        }
        // 贪心选列
        for(int j = 1; j <= m; j++)
            col[j] = b[n+1][j];
        sort(col+1, col+m+1, greater<int>());
        for(int j = 1; j <= cnt1; j++)
            cnt += col[j];

        ans = max(ans, cnt);
    }

    printf("%d", ans);

    return 0;
}