题目传送门
思路:
- 题目说我们选某几列,某几行,使得我们获得的权值最大。
- 那么我们二进制枚举行,例如有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;
}
}
}
LL col[maxn];
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;
}