每日一题 矩阵消除游戏 (二进制枚举)

一.题意

二.题解

由于数据很小，所以可以直接暴力枚举
这里我选择的是二进制枚举选取了哪些列
每次枚举记录得分以及每行剩下的分数
然后对 n 行分数进行排序
取剩下次数的前 k 大行
加上对应行的分数即可

三.代码:

#include<bits/stdc++.h>
#include<string>
#include<cstring>
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#define IOS ios::sync_with_stdio(false);cin.tie(0)
//#define ll long long
#define ll unsigned long long
#define inf 0x3f3f3f3f
#define mod 1000000007
#define eps 1e-6
#define pi acos(-1)
#define mysetit multiset<ll>::iterator
#define mymsetit multiset<ll>::iterator
#define mymapit map<ll,ll>::iterator
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define lowbit(x) (x&(-x))
#define mp make_pair
#define pb push_back
#define si size()
#define E exp(1.0)
#define fixed cout.setf(ios::fixed)
#define fixeds(x) setprecision(x)
using namespace std;
inline ll read(){
   ll s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
void put1(){ puts("YES") ;}
void put2(){ puts("NO") ;}
void put3(){ puts("-1"); }
using namespace std;
ll qpf(ll a, ll b, ll p)
{ll ret = 0;while(b){if(b & 1) ret = (ret + a) % p;
a = (a + a) % p;b >>= 1;}return ret % p ;}
ll qp(ll a, ll n, ll p)
{ll ret = 1;while(n){if(n & 1) ret = qpf(ret, a, p);a = qpf(a, a, p);
n >>= 1;}return ret % p ;}

const int manx=100;
ll a[manx][manx];
ll c[manx];
int main(){
    ll n=read(),m=read(),k=read(),s=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            a[i][j]=read();
    k=min(k,min(n,m));
    ll ans=0;
    for(int t=0;t< 1<<m; t++){ //枚举子集 代表 选取了那几列
        ll cnt =__builtin_popcountll(t);
        if(cnt>k) continue;
        ll res=0;
        for(int i=1;i<=n;i++)
            for(int j=0;j<m;j++){
                if( 1<<j & t ) res+=a[i][j+1];
                else c[i]+=a[i][j+1];
            }
        sort(c+1,c+1+n);
        reverse(c+1,c+1+n);
        for(int i=1;i<=k-cnt;i++)
            res+=c[i];
        ans=max(ans,res);
        memset(c,0,sizeof(c));
    }
    printf("%lld\n",ans);
    return 0;
}