牛客练习赛58 C题矩阵消除游戏题解

https://ac.nowcoder.com/acm/contest/4090/C
估计这种基础题的题解不会有太多人需要，尤其是我这种叨叨叨的话痨题解更不会有太多人看，我来写个这个题的题解，主要是纪念一下时隔大半年打比赛的各种手残脑残，以及证明一下我已经回坑啦……
认真题解：
———————如果你只是想看本题题解不看分析可以直接跳到下一个分割线———————

    ——没有交叉只能保证选的数字最多，但是未必的最大的，例如：
    3 3 2
    1 5 1
    5 5 5
    第四，如果我每次贪心的选剩下的图中最大的一行或者一列，然后把这一行（列）抹为0可以吗？（既按照题目描述步骤每一步贪心，这样的局部最优解能得到全局最优解吗？）
    我想这又是一个可能会坑到的地方。
    先也给一组反例：
    4 4 3
    1 1 9 3
    1 8 10 8
    再多说两句，当你有这种怀疑却不知道对不对的时候怎么办呢？
    严肃认真的方法是争取数学证明……但是这个方法我其实不太推荐，因为在贪心的方法对的时候，归纳法一般比较好证，但是要归纳法你没证明出来你就能说他不对吗？完全有可能是因为不会证……（痛苦而真实的领悟，都是我血的教训）
    那么在没法证明又怀疑的时候最好的办法是举反例，举反例不是随便举例子，是要从你的怀疑入手。以本题为例，什么情况容易出现反例？我怀疑的就是某一行或者列有几个数特别大，然后第一次就把他们一起选了，然而事实上可以通过后面的选择分开选这几个数。有了这种怀疑之后，你可以轻轻松松举出一堆反例，如：
    3 3 2
    100 100 1
    2 4 2
    4 2 2
—————————————以下就是本题解法的分隔线—————————————
    我们知道如果只是行的选择或者只是列的选择就可以贪心（这个太显然了，本人任性，不证）。那么我们就把问题转化成只选若干列好了！
    如果我们想贪心的选取最好的若干列，那么我们必须提前知道我们选了多少行哪些行，这个怎么知道呢？看看数据范围，其实暴力就好了——写个搜索，或者用01串枚举。
    搜索我就不说了哈（懒癌晚期），我来细细讲讲01串枚举：
    所谓01串枚举，就是我们在每个个体都面对两种选择的时候，可以用一个01串表示，比如说对于本题，每一行有选和不选两种可能，假设有5行的话，我们就可以用一个长度为5的01串来表示，0表示不选1表示选，就像一个bool数组一样，如：01001 表明第134行不选，第25行要选。
    只是用一个数字来表示比用数字表示方便，为什么方便呢？因为所有长度小于n的01串，转成十进制之后就是所有小于的数字，这样从0到枚举数字就是从00…00枚举到11…11。这样比写个搜索枚举所有选和不选的情况快乐吧！
    具体细节在代码里面有注释。

#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++; 
            b[i] =1;
        }
        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;

}

最后说一下我今晚是怎么wa到想哭的：
    第一个找出来的错误：读入数据的时候行和列的循环范围都写成了n……偷懒复制粘贴需谨慎！
    第二个是枚举行的范围写成了0到……
    第三个错误就是上面提到的那个k比较大的时候都continue掉了……