NC200190 矩阵消除游戏(二进制枚举)

题目链接

题意：



题解：






AC代码

/*
    Author : zzugzx
    Lang : C++
    Blog : blog.csdn.net/qq_43756519
*/
#include<bits/stdc++.h>
using namespace std;
#define lson now<<1
#define rson now<<1|1
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod=1e9+7;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=2e5+10;
const ll inf=0x3f3f3f3f;
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
ll a[20][20],sum[20],b[20][20];
bool cmp(int a,int b){return a>b;}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n,m,t;
    cin>>n>>m>>t;
    ll s=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>a[i][j],s+=a[i][j];
    if(t>=min(n,m)){cout<<s<<endl;return 0;}
    ll ans=0;
    for(int i=0;i<(1<<n);i++){
        ll tmp=0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                b[i][j]=a[i][j];
        int p=0;
        for(int j=0;j<n;j++)
            if((i>>j)&1){
                p++;
                for(int k=1;k<=m;k++)
                    tmp+=b[j+1][k],b[j+1][k]=0;
            }
        if(p>t)continue;
        for(int j=1;j<=m;j++){
            sum[j]=0;
            for(int k=1;k<=n;k++)
            sum[j]+=b[k][j];
        }
        sort(sum+1,sum+1+m,cmp);
        for(int j=1;j<=t-p;j++)
            tmp+=sum[j];
        ans=max(ans,tmp);
    }
    cout<<ans<<endl;

}