题解 | #矩阵消除游戏#

本题的思路是，通过位运算来枚举选行还是选列，然后用一个数组存下每个位运算，也能算出有多少个选列，先用一个数组存下每个行，然后再把选入的行相加，然后把没有选入行的列数相加入进去一个数组，然后再排序一下，把满足条件的列数加入进去，然后再维护最大值。。。

# include <iostream>
# include <algorithm>
# include <cstring>
# include <cstdio>
using namespace std;
const int N=20;
long long sh[N],sl[N];
int s[N][N];
int n,m,k;
long long ans=0;
int b[N];
int deal(int t){
    memset(b,0,sizeof(b));
    int cnt=0;
    int i=1;
    while(t){
        if((t&1)) {
          cnt++;
          b[i]=1;
        }
        t>>=1;
        i++;
    }
    return cnt;
}
int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%d",&s[i][j]);
            sh[i]+=s[i][j];
        }
    }
    if(k>n) k=n;
    if(k>m) k=m;
    int num=(1<<n)-1;
    long long sum=0;
    for(int i=0;i<=num;i++){
        sum=0;
        int temp=deal(i);
        int temp2=k-temp;
        if(temp2<0||temp2>m) continue;
        for(int i=1;i<=n;i++){
            if(b[i]) sum+=sh[i];
        }
        memset(sl,0,sizeof(sl));
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(!b[i]){
                    sl[j]+=s[i][j];
                }
            }
        }
        sort(sl,sl+m+1);
        for(int i=m,j=1;j<=temp2;i--,j++){
            sum+=sl[i];
        }
        ans=max(ans,sum);
    }
    printf("%d\n",ans);
    return 0;
}

总结： 听了思路之后，但还是不太会写，代码力太弱了，看来要多做这种有挑战性的题目。。其实选入行不用改变他的值，因为不需要去选他就行，，然后把列数加入进去就行。。