当前位置： 移动技术网 > 移动技术>移动开发>Android > 矩阵消除（二进制枚举，贪心）

矩阵消除（二进制枚举，贪心）

2020年07月09日  | 移动技术网移动技术  | 我要评论

题目传送门

文章目录

思路：

  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;
}

本文地址：https://blog.csdn.net/qq_45769627/article/details/107209521

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网