#枚举 #位运算 #贪心

题意

• n行m列矩阵(1<=n,m<=15)，k次操作，每次消除一行or一列，将答案加上消除的值
• 求解最大答案

思路

• 对于只消除行和列，一定是消除行和和列和最高的k个
• 行和列同时选的时候，贪心的依次选最高行和列不能保证答案最优

选两次
9 10 1
1 1 1
1 20 9

• 所以既然混着选没法确定，那就枚举行的所有选法，然后再行确定的时候堆列进行贪心，用一个n位2进制表示行的选法，然后每次剔除所选行的元素计算每列的和

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;

int a[20][20];
int sum1[20],sum2[20];

int deal(int x){
    int cnt=0;
    while(x){
        if(x&1) cnt++;
        x>>=1;
    }
    return cnt;
}

signed main(){
    int n,m,k;
    cin >> n >> m >> k;
    if(k>n||k>m) k=n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin >> a[i][j];
            sum1[i]+=a[i][j];
        }
    }
    int res=0;
    for(int st=0;st<=(1<<n)-1;st++){
        int cnt=deal(st);
        int ans=0;
        if(cnt>k) continue;
        for(int i=1;i<=n;i++){
            if((st>>i-1)&1){
                ans+=sum1[i];
            }
        }
        // cout << st << ' ' << cnt << ' '<< ans << endl;
        memset(sum2,0,sizeof(sum2));
        for(int i=1;i<=n;i++){
            if((st>>i-1)&1) continue;
            for(int j=1;j<=m;j++){
                sum2[j]+=a[i][j];    
            }
        }
        sort(sum2+1,sum2+m+1,greater());
        
        for(int i=1;i<=k-cnt;i++){
            ans+=sum2[i];
        }
        res=max(res,ans);
    }
    cout << res << endl;
    return 0;
}