矩阵消除游戏

解题思路：

因为横竖之间的删减会相互影响，所以采用先枚举后贪心的方法。 先枚举所有行的情况（用一个01串表示这哪几行被选中很好避免好几层for循环的方法），在选择最多的前几列

AC代码：

#include<bits/stdc++.h>
using namespace std;
int i,j,n,m,k,a[20][20],lie[20],sum=0,ans=0;
int cnt=0;
int jisuan(int st){
	sum=0;
	for(int i=0;i<n;i++){
		if(((st>>i)&1)==1){//如果这一行被选中，((st>>i)&1)==1用来判断最后一位是否是1
			for(int j=0;j<m;j++) sum+=a[i][j];
			cnt++;
		}
		else{//没被选中
			for(int j=0;j<m;j++) lie[j]+=a[i][j];//lie[]用来记录每一列的和
		}
	}
	return sum;
}
int main(){	
	scanf("%d%d%d",&n,&m,&k);
	for(i=0;i<n;i++){
		for(j=0;j<m;j++){
			scanf("%d",&a[i][j]);
			sum+=a[i][j];
		}
	}
	if(n<=k||m<=k){//如果k足够大，可以将所有数都选择掉就直接输出sum
		cout<<sum<<endl;
		return 0;//可以直接结束程序
	}
	for(int st=0;st<=((1<<n)-1);st++){//列举每一种情况
		cnt=0;//cnt表示有几行被选中
		memset(lie,0,sizeof lie);//每种情况都要更新
		sum=jisuan(st);//算出选中行的和
		int rest=k-cnt;//还剩几次可以选
		if(rest<0) continue;//次数超了情况不可能
		sort(lie,lie+m);//从小到大排列
		for(j=m-1,i=0;i<rest;i++,j--){//加上前rest个和最大的列
			sum+=lie[j];
		}
		ans=max(ans,sum);
	}
	cout<<ans<<endl;
	return 0;
} 

如何用01串表示选中情况

for(st=0;st<=((1<<n)-1);st++){
	//(1<<n)-1表示n个1
}