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

发表于 更新于 分类于

链接

https://ac.nowcoder.com/acm/contest/4090/C

题意

有一个 $n \times m$ 的矩阵，进行 $k$ 次操作，每次可以选一行（列）使 $res$ 加上这一行（列）的权值和并将这一行（列）的单源格的权值都变为 $0$，求 $res$ 的最大值

思路

首先 $k=\min(k,\min(n,m))$，因为当 $k=n∣∣k=m$ 时我们就可以将所有行（列）全部选择

状压枚举选择了哪几列，再计算每一行中剩余元素的和进行排序，在根据值从大到小选即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
using namespace std;
const int N=20;
int n,m,t,a[N][N],sum[N],ans;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>t;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin>>a[i][j];
    t=min(t,min(n,m));
    for(int i=0;i<(1<<m);i++) {
        int cnt=__builtin_popcount(i);
        int res=0;
        if(cnt>t) continue;
        memset(sum,0,sizeof sum);
        for(int j=0;j<n;j++)
            for(int k=0;k<m;k++) {
                if(i&1<<k) res+=a[j][k];
                else sum[j]+=a[j][k];
            }
        sort(sum,sum+n);
        for(int j=n-1,k=t-cnt;k;j--,k--) res+=sum[j];
        ans=max(ans,res);
    }
    cout<<ans<<endl;
     return 0;
}