android开发分享矩阵消除（二进制枚举，贪心）

题目传送门

思路：

1. 题目说我们选某几列，某几行，使得我们获得的权值最大。
2. 那么我们二进制枚举行，例如有4*4的矩阵，k=4, 1010表示，1行和第4行需要选，剩下2个选列，对应行置为0。那么再取处理后的矩阵的权值和前2大的列即可

AC代码：

#include <bits/stdc++.h>  using namespace std; typedef long long LL; const int maxn = 200; int a[maxn][maxn]; LL ans = -1e18; int main() {    std::ios::sync_with_stdio(false);    int n,m,k;    cin>>n>>m>>k;    LL all = 0;    for(int i=1;i<=n;i++)    {        for(int j=1;j<=m;j++)        {            cin>>a[i][j];            all+=a[i][j];        }    }    if(k>=n||k>=m)    {        cout<<all<<endl;        return 0;    }    int e = 1<<n;    //进行二进制枚举行    for(int i=0;i<e;i++)    {        int x = i;        int b[maxn];        memset(b,0,sizeof(b));        int e2 = n;        int cnt = 0;        while(x)        {            b[e2--] = x&1;            if(b[e2+1]) cnt++;            x>>=1;        }        LL sum = 0;        if(cnt>k) continue;         int a2[maxn][maxn];         memset(a2,0,sizeof(a2));         for(int r=1;r<=n;r++)         {             for(int c= 1;c<=m;c++)         {             a2[r][c] = a[r][c];         }          }         //处理要选的行        for(int r=1;r<=n;r++)        {            if(b[r])            {                for(int c=1;c<=m;c++)                {                    sum+=a2[r][c];                    a2[r][c] = 0;                }            }        }        //剩下的k-cnt都是枚举列        LL col[maxn];//根据k的范围来确定大小，容易越界        memset(col,0,sizeof(col));        for(int j=1;j<=m;j++)        {            for(int k=1;k<=n;k++)            {                col[j]+= a2[k][j];            }        }        //从大到小排列        sort(col+1,col+m+1,greater<LL>());        for(int j=1;j<=k-cnt;j++)        {             sum+=col[j];        }         ans = max(ans,sum);    }    cout<<ans<<endl;    return 0; }