矩阵消除游戏

思路

这个题其实不能贪心, 看了下 M 和 N 更像是一道暴力搜索的题目

怎么搜索呢

用 01状态压缩, 枚举选哪些行, 然后选剩下的列(取值最大的几个就好)

记录两个值, 一个是行和sum (分开每行记也行) 另一个是列和 sumrow[r] 记录每一列的 列和

然后枚举找最大值即可 , 时间复杂度 O(2^n * n * m ) 可以接受

ac 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int inf = INT_MAX;
typedef pair<int, int> pii;
typedef priority_queue<int, vector<int>, greater<int>> small_heap;
#define int long long
int n, m, k;
int a[20][20];
int b[20][20];
int ans;
int sumrow[20];
int cnt;
bool cmp(int a, int b)
{
    return a > b;
}
int get(int st)
{
    memcpy(b, a,sizeof a );
    cnt = 0;
    int sum = 0;
    memset(sumrow, 0, sizeof sumrow);
    for (int c = 1; c <= n; c++)
    {
        if (st >> (c - 1) & 1)
        {
            cnt++;
            for (int r = 1; r <= m; r++){
                sum += b[c][r];
                b[c][r] = 0;
            }
        }
        else
        {
            for (int r = 1; r <= m; r++)
                sumrow[r] += b[c][r];
        }
    }
    return sum;
}
int32_t main()
{
    int su = 0;
    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]);
            su += a[i][j];
        }
    
    if (k  >= n || k >= m  ) 
    {
        printf("%d\n" , su);
        return 0;
    }
    for (int s = 0; s <= ((1 << n) - 1); s++)
    {
        int sum = get(s);
        int rest = k - cnt;
        if (rest < 0)
            continue;
        sort(sumrow + 1, sumrow + m + 1, cmp);
        for (int i = 1; i <= rest; i++)
            sum += sumrow[i];
        ans = max(ans, sum);
    }
    printf("%d\n", ans);
    return 0;
}