题目描述

牛妹在玩一个名为矩阵消除的游戏，矩阵的大小是n{n}n行m{m}m列，第i{i}i行第j{j}j列的单元格的权值为ai,ja_{i,j}ai,j，牛妹可以进行k{k}k个回合的游戏，在每个回合，牛妹可以选择一行或者选择一列，然后将这一行或者这一列的所有单元格中的权值变为0{0}0，同时牛妹的分数会加上这一行或者这一列中的所有单元格的权值的和。

牛妹想最大化她的得分，球球你帮帮她吧！

输入描述: 

第一行三个整数n,m,k{n,m,k}n,m,k 接下来n{n}n行每行m{m}m个整数表示矩阵中各个单元格的权值。

输出描述: 

输出一个整数表示牛妹能获得的最大分数。
示例1

输入

复制 3 3 2 101 1 102 1 202 1 100 8 100 
3 3 2
101 1 102
1 202 1
100 8 100

输出

复制 414 
414

备注: 

		
		
		

			1≤n,m≤151\leq n,m\leq 151≤n,m≤15 
		


		

			1≤ai,j≤1e61\leq a_{i,j}\leq 1e61≤ai,j≤1e6 
		

1≤k≤n∗m1\leq k\leq n*m1≤k≤n∗m

思路

先枚举选行的所有可能性，如果还能选的话，就贪心地选最大的那几列，取每次的最大值就行了。

代码 

//矩阵消除游戏(枚举 贪心) 
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 20;

int a[N][N];
int n , m , k;
bool selects[N];
int row[N] , line[N];

bool cmp(int a , int b)
{
	return a > b;
}

int work(int num)
{
	int cnt = 0;
	for(int i = 0 ; i < n ; i++ , num /= 2)
	{
		selects[i] = false;
		if(num & 1)
		{
			cnt++;
			selects[i] = true;
		}
		//cout<<selects[i];
	}
	//cout<<endl;
	return cnt;
}

int main()
{
	scanf("%d %d %d" , &n , &m , &k);
	for(int i = 0 ; i < n ; i++)
	{
		for(int j = 0 ; j < m ; j++)
		{
			scanf("%d" , &a[i][j]);
			row[i] += a[i][j];
		}
	}
	
	int ans = 0;
	if(k >= n || k >= m)
	{
		for(int i = 0 ; i < n ; i++)
			ans += row[i];
		printf("%d\n" , ans);
		return 0;	
	}
	
	int maxn = (1 << n) - 1;
	for(int x = 0 ; x <= maxn ; x++)
	{
		int row_num = work(x);
		int line_num = k - row_num;
		if(row_num > k)
			continue;
		
		int sum = 0;
		for(int i = 0 ; i < n ; i++)
		{
			if(selects[i])
				sum += row[i];
		}
		
		for(int i = 0 ; i < m ; i++)
			line[i] = 0;
		
		for(int i = 0 ; i < n ; i++)
		{
			for(int j = 0 ; j < m ; j++)
			{
				if(!selects[i])
					line[j] += a[i][j];
			}
		}
		
		sort(line , line + m , cmp);
		for(int i = 0 ; i < line_num ; i++)
			sum += line[i];
		ans = max(ans , sum);
	}
	
	printf("%d\n" , ans);
	return 0;
}