题解 | #矩阵消除游戏#

这个题不能胡乱选择行或者列，因为你一旦选择了一列以后，接下来选一行一定会受到影响，不符合贪心的特点，就是子问题的求解不影响其他部分。所以可以枚举行，然后贪心列，这样列和列之间不会相互影响，可以贪心的来做，然后就是位运算枚举每一种行的选择情况。

这道题被坑了，主要还是基础知识不扎实，deal函数我直接把数组传进去，我以为里面变，不会影响外面的数组，然后就WA了两个小时，一直以为是什么逻辑上的问题，直到我突发奇想，想把数组输出出来看看，结果@_@ 很难过，所以数组一定要copy一份出来 （QaQ）

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
const int M=20;
int a[M][M];
int hang[M];
int lie[M];
int sum;
bool cmp(int a,int b){
	return a>b;
}
long long deal( int c[], int b[],int num){
	int h[M];
	int l[M];
	memcpy(h,c,n*sizeof(int));
	memcpy(l,b,m*sizeof(int));
	int pos[M]={0};
	int cnt=0;
	long long sum=0;
	int tot=0;
	while(num){
		if((num&(-num))==1){
			pos[tot++]=cnt;
			sum+=h[cnt];
		}
		num>>=1;
		cnt++;
	}
	for(int i=0;i<m;i++){
		for(int j=0;j<tot;j++){
			l[i]-=a[pos[j]][i];
		}
	}
	sort(l,l+m,cmp);
	for(int i=0;i<k-tot;i++){
		sum+=l[i];
	}
	return sum;
}
int numb(int num){
    int cnt=0;
    while(num){
        if((num&(-num))==1){
            cnt++;
        }
        num>>=1;
    }
    return cnt;
}
int main(){
	cin>>n>>m>>k;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>a[i][j];
			hang[i]+=a[i][j];
            sum+=a[i][j];
		}
	}
    if(n<=k||m<=k){
       cout<<sum<<endl;
        return 0;
    }
	for(int j=0;j<m;j++){
		for(int i=0;i<n;i++){
			lie[j]+=a[i][j];
		}
	}
	long long ans=0;
	for(int i=0;i<=(1<<n)-2;i++){
        if(numb(i)>k)continue;
		ans=max(ans,deal(hang,lie,i));
	}
	cout<<ans<<endl;
	return 0;
}