题解 | #矩阵消除游戏#

题目的难点在于，当牛妹消除某一行时，会影响每一列和的大小。我们不妨先选定要消除的行，再改变这些行影响的列，最后对列进行贪心，而不是同时关注行和列的变化。
我们枚举出消除行的每一种情况，并计算在这些情况下我们是否可以继续加上一些列、要加上哪些列（排序）。

#include<iostream>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;

int a[20][20];
int col[20];
int n,m,k;
int cnt=0;//当前选了几行
bool cmp(int x,int y)
{
    return x>y;
}
int calc(int x)
{
    int sum=0;
    for(int i=0;i<n;i++)
    {
        if(x>>i&1==1) 
        {
            for(int j=0;j<m;j++) sum+=a[i][j];
            cnt++;
        }
        else{
            for(int j=0;j<m;j++) col[j]+=a[i][j];
        }   
    }
    return sum;
}
int main()
{
    
    scanf("%d%d%d",&n,&m,&k);
    int tempsum=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            scanf("%d",&a[i][j]);
            tempsum+=a[i][j];
        }
    }
    if(m<=k||n<=k) 
    {
        cout<<tempsum;
        return 0;
    }
    int res=0;
    for(int i=0;i<(1<<n);i++)
    {
        memset(col,0,sizeof(col));
        cnt=0;
        int sum=calc(i);
        int cntcol=k-cnt;
        if(cnt>k||cntcol>m) continue;
        else
        {
            
            sort(col,col+m,cmp);
            for(int i=0;i<cntcol;i++) sum+=col[i];
        }
        res=max(sum,res);
    }
    
 
    printf("%d",res);
}