【每日一题】8月11日题目精讲—矩阵消除游戏

来源：牛客网：

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

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

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

输入描述:
第一行三个整数n,m,k
接下来n行每行m个整数表示矩阵中各个单元格的权值。
输出描述:
输出一个整数表示牛妹能获得的最大分数。
示例1
输入
复制

输出
复制

备注:
在这里插入图片描述

题解：

我来总结下官方题解：
如果我们考虑一行一行或一列一列的选择则可以贪心。但实际上不行，所以我们要把问题转化成选若干列
再看看范围1<n,m<15，这不是等着我们去暴力吗？
如果我们给出每一列，那每一列的状态就是固定的
我们可以用01串来表示状态，比如01001表示134行不选，第25行选择，这样我们直接枚举0到2^n^-1就代表枚举了00...00到11....11
大致过程：
T从0~2^n^-1枚举，表示行的状态
T是一个十进制数，我们转发成二进制，看里面几个1（numh），哪些位置是1，进行记录。
T中几个1说明选几行，numl=k-numh（T中1的个数）为选几列
sum先加上要选的那几行（T中1的位置）
然后刨去那几行的数据，我们对剩下的数据按照每列的和进行排序，选择最高的那numl列
维护答案即可
整个过程实则为二进制转换+贪心

代码：

我对官方代码进行了更详细的解读

#include<bits/stdc++.h>
using namespace std;
int n, m ,k;
int a[20][20];
long long sh[20],sl[20];//sh[i]是第i行的和，sl[i]是第i列的和（在行选完之后用）
bool b[20];//b[i]是01串转换过来的bool数组（用bool数组主要是为了方便大家理解）
long long ans = 0; //存答案，注意总和会超过int的最大值要用long long
int deal(int x)  //把x这个数字转换成bool数组
{
    memset(b, 0, sizeof(b)); //不清数组会死！
    int cnt = 0, i = 1; //cnt存01串里面1的个数
    while (x)
    {
        if (x&1)  //如果x的最后一位是1
        {
            cnt++;//记录其中1的数量 
            b[i] =1;//说明第i行是被选择的 
        }
        x>>=1;  //x右移一位，等价于除以二取整
        i++;//到下一行 
    }
    return cnt;
}
int main()
{
//————————————读入——————————————
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
    {
        scanf("%d", &a[i][j]);
        sh[i] += a[i][j];//记录每一行的值 
    }
//————————以上读入不多说————————

//——如果k>n或者k>M，那么肯定就把矩阵选完了————
//这里我这么处理主要是因为我后面的有个判断把这种情况给直接continue掉了，
//debug的时候不想的再写别的了就这样了
//k=n或者m就已经能把矩阵选完，所以结果肯定是一样的
    if (k > n) k = n;
    if (k > m) k = m;
//————————————————————————————————————————

//—————枚举选行的所有可能性，贪心处理列——————
    int tmp = (1<<n) -1;  //1<<n就等于2^n，位运算不会的同学百度一下
    for (int T =0; T <= tmp; T++)  //T用来枚举行的状态
    {
        int numh = deal(T);//将状态T转为bool数组，并返回有多少个1，既要选多少行
        int numl = k-numh; //numl是要选多少列
        if (numl > m || numl < 0) continue;
        //numl>m或者numl<0，说明行的方案不对（其实也有可能是k太大，这里就是上文说的k比较大的时候直接continue没了的地方）。

        long long  sum=0;  //sum是本次枚举的方案的和
        for (int i = 1; i <= n; i++) 
            if (b[i]) sum += sh[i]; //把选中的行都加上

        memset(sl, 0, sizeof(sl));//行选得不同矩阵就不同，所以sl数组每次都要清干净
        for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (!b[i]) sl[j] += a[i][j]; //第i行没有选，j列的和需要加上a[i][j]（第i行选了a[i][j]就清零了不能加）
        sort(sl+1, sl+1+m);//对每一列的和进行排序（刨去指定行） 
        for (int i=1,j=m; i<=numl; i++,j--) sum += sl[j]; //把最大的numl列的和加到方案里
        ans = max(ans, sum);//维护答案
    }
//————————————枚举+贪心结束——————————————
    printf("%lld\n", ans);
    return 0;

}