矩阵消除游戏

题目描述

牛妹在玩一个名为矩阵消除的游戏，矩阵的大小是行列，第行第列的单元格的权值为，牛妹可以进行个回合的游戏，在每个回合，牛妹可以选择一行或者选择一列，然后将这一行或者这一列的所有单元格中的权值变为，同时牛妹的分数会加上这一行或者这一列中的所有单元格的权值的和。

牛妹想最大化她的得分，球球你帮帮她吧！

输入描述:

第一行三个整数n,m,k
接下来n行每h行m个整数表示矩阵中各个单元格的权值。

输出描述:

输出一个整数表示牛妹能获得的最大分数。

题解

为什么不能贪心的每次找行或列的最大值
因为选列行或列之和，对列或行有影响，即选不同的行产生的最大不一样
也就是不满足无后效性
故贪心有问题

发现数据只有15，直接枚举所有情况即可
通过二进制枚举我们选择哪几行
假设该次枚举cnt行，那么剩下的肯定都选的是列，那么我们就可以贪心的选取列了。只用找到枚举完行之后，剩余每列之和的前k-cnt大的加在总和里即可

代码

#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pb push_back
#define pii pair<int,int>
#define all(A) A.begin(), A.end()
#define fi first
#define se second
#define MP make_pair
#define rep(i,n) for(register int i=0;i<(n);++i)
#define repi(i,a,b) for(register int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(register int i=int(b);i>=(a);--i)
template<typename T>
inline T read(){
    T s=0,f=1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f=-1;ch = getchar();}
    while(isdigit(ch)) {s=(s<<3)+(s<<1)+ch-48;ch = getchar();}
    return s*f;
}
#define gn() read<int>()
#define gl() read<ll>()
template<typename T>
inline void print(T x) {
    if(x<0) putchar('-'), x=-x;
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
////////////////////////////////////////////////////////////////////////
const int N=2e5+100;
const int mod=1e9+7;
ll b[20];
ll a[20][20],sum[20];
ll ans=0;
int solve(int k){
    int index=1;
    int cnt=0;
    fill(b,b+20,1);
    while(k){
        if(k&1)b[index]=0,++cnt;
        k>>=1;
        ++index;
    }
    return cnt;
}
////////////////////////////////////////////////////////////////////////
int main(){
    int n=gn(),m=gn(),k=gn();
    if(k>n)k=n;
    if(k>m)k=m;//注意这两句 特判一下
    repi(i,1,n){
        repi(j,1,m){
            a[i][j]=gl();
            sum[i]+=a[i][j];
        }
    }
    for(int i=0,len=(1<<n)-1;i<=len;++i){
        int count=solve(i);
        if(count>k)continue;
        ll num=0;
        repi(i,1,n){
            if(!b[i])num+=sum[i];
        }
        priority_queue<int> q;
        repi(i,1,m){
            int z=0;
            repi(j,1,n){
                z+=a[j][i]*b[j];
            }
            q.push(z);
        }
        repi(i,count+1,k){
            num+=q.top();
            q.pop();
        }
        ans=max(ans,num);
    }
    print(ans);
}
/**
* In every life we have some trouble
* When you worry you make it double
* Don't worry,be happy.
**/