NC200190 矩阵消除游戏-枚举的同时贪心求最优结果

#include <bits/stdc++.h>

using namespace std;

int mapp[20][20];
int hang[20];
int main(void)
{
	int n,m,k;
	cin>>n>>m>>k;
	for (int i=1;i<=n;i++)
	for (int j=1;j<=m;j++)
	{
		cin>>mapp[i][j];
	}
	k=min(k,min(n,m));
	int ans=0;
	for (int st=0;st<(1<<m);st++) //位运算枚举所要选取的列 
	{
		int sum=0;
		int num=__builtin_popcount(st);
		if (num>k) continue;
		memset(hang,0,sizeof(hang));
		for (int i=0;i<m;i++)
		{
			if ((1<<i)&st) //注意！不能误写成((1<<i)&st==1)  (1<<i)&st的结果非零即可 
			{
				for (int j=1;j<=n;j++)
				{
					sum+=mapp[j][i+1];
				}
			}
			else
			{
				for (int j=1;j<=n;j++)
				{
					hang[j]+=mapp[j][i+1]; //在该列不选取时，顺便把不选取的列对应的每一行的和求出来 
				}
			}
		}
		sort(hang+1,hang+1+n,greater<int>()); //位运算枚举要选取的列，排序后贪心行 
		for (int s=1;s<=k-num;s++)
			sum+=hang[s];
		ans=max(ans,sum);
	}
	cout<<ans<<endl;
}