题目链接

https://ac.nowcoder.com/acm/problem/200190

分析题目

从矩阵中取一整行或一整列，把选到的行或列每个位置上的权取走，意味着你的sum加上当前位置的 值，而矩阵中此位置的值会置零，也就是每一步操作对后续矩阵是有影响的。问取k次行或者列，问取得的最大值是多少。

思路讲解

假如k很大，即可以取无穷多次，显然整个矩阵被取完了，结果就是整个矩阵的和。试着缩小k的范围，如果我们都取行的话，当k=n行数时，就可以把矩阵都取完了；如果我们都取列的话，当k=m列数时，就可以把矩阵都取完了，因此，只要k>=min{n，m}，我们就可以把整个矩阵取完，这种情况下，我们直接输出矩阵和，并结束程序就行了。
要是k<min{n，m}。我们就枚举，枚举行的所有取法，对于每一种行的取法，取列的时候，我们在当前行取法的情况下，取最大的若干个除去行列相交处的值的列之和，行列相加找最大值就是答案。（这么说起来其实挺绕的，下一个模块配合代码讲会好点）
大致过程：
step1：枚举行取法
step2：累加被选区的行之和
step3：将除去相交处的每个列元素之和从大到小排序
step4：行列相加，max找答案

过程实现

tmp_sum用来存储整个矩阵的和。
a数组存储每个位置的值。
sh[i]表示第i行之和。
sl[i]表示第i列之和。是除去取行操作已经取走的位置的列之和。举个例子：已经取走了第i行，当你要用sl[j]存储第j列之和的时候，其存储的是第j列之和-a[i][j]，即sl[j]=第j列之和-a[i][j]。

AC代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n, m ,k;
int a[20][20];
ll sh[20], sl[20];
ll ans = 0,tmp_sum = 0;
bool cmp(ll a, ll b){
    return a > b;
}
int main()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++){
            cin >> a[i][j];
            sh[i] += a[i][j];//求行之和
            tmp_sum += a[i][j];
        }
    if(k >= min(n, m)) {cout << tmp_sum; return 0;}
    //k>=min{n，m}，可以把整个矩阵取完

    int bound = (1<<n) -1; 
    //用二进制的方式去枚举行的取法
    //举例：000001代表取第一行，其他行不取；000011代表取第一、二行，其他行不取
    //因此只要从0……0到1……1遍历一遍就是所有的行取法了
    for (int h =0; h <= bound; h++)
    {
        int cnt = 0;
        ll sum = 0;
        for (int i=1;i<=n;i++){
            if (((h >> (i-1)) &1) == 1){
            //第i行如果是1，意味着取第i行，sum就加上整行，记录取行的个数cnt++
            //这里感觉会比较难理解，
            //大概意思就是，h右移i-1位后，最后一位就是第i行对应的取法，
            //1是取，0是不取，通过&1与1判等操作，实现判断最后第i行取还是不取
                sum += sh[i];
                cnt ++;
            }
        }

        if (k<cnt) continue; 
        //注意，要是取的行数大于k了，此种情况不存在，continue

        memset(sl, 0, sizeof(sl));//记住清零
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                if (((h >> (i-1)) &1) == 0) sl[j] += a[i][j]; 
                //遍历所有点，如果当前点所在行i没被取，
                //那么列之和就可以加上这个点的值
                //反之，如果当前点所在行i被取走了，此位置已经变为0了，
                //列之和就不能加上这个点的值

        sort(sl+1, sl+1+m, cmp);
        //因为行的取法已经确定，所有我们只要找出当前行取法时，若干个最大的列之和即可
        for (int i=1; i<=k-cnt; i++) sum += sl[i]; 
        //前文所说的若干个就是k-所选行数，之所以不提前说是因为会把思路弄得更乱
        ans = max(ans, sum);
    }
    cout << ans;
    return 0;
}

哔哔赖赖

二刷，还是没刷出来，悲哀……
仿照大佬的又写了一遍，debug还de了好久，才发现没计算sh数组……
我好菜啊！
最后的最后，我还想问上天一句：我什么时候才能成为大佬啊啊啊！！！