題目鏈接：https://ac.nowcoder.com/acm/problem/200190
題目大意
n*m的矩陣，牛妹每次操作可以消去一行或者消去一列，獲得該行/列矩陣的分數，順便清零，最多k次操作問你可以獲得最高分數是多少，
1<=n,m<=15;1<=ai<=1e6;1<=k<=n*m
思路
n和m給的范圍很小，可以對行進行二進制列舉，如5(101)表示消去第1行和第3行，然后還剩k-2次操作，那么對剩下每列總和排個序，取前k-2大的數求和，更新最大值，
特判k大于等于nm較小值，因為可以全部消完直接輸出總和即可，
ac代碼
#include<bits/stdc++.h>
using namespace std;
#define io cin.tie(0);ios::sync_with_stdio(false);
#define ok(x, y) x >= 1 && x <= n && y >= 1 && y <= m
#define debug(x) cout<<#x<<"="<<x<<endl
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define mk make_pair
#define ll long long
#define ull unsigned long long
#define lb long double
#define rs p<<1|1
#define ls p<<1
#define eps 1e-6
#define pi acos(-1)
const int maxn = 1e5 + 5;
const int maxm = 1e6 + 5;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
const int bas = 2333;
inline ll read(){
ll p=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){p=(p<<1)+(p<<3)+(c^48),c=getchar();}
return f*p;
}
void print(__int128 x){
if(x<0) {putchar('-'); x=-x;}
if (x>9) print(x/10);
putchar('0'+x%10);
}
int a[25][25], sum[25], tmp[25];
void solve(){
int n, m, k;
cin >> n >> m >> k;
memset(sum, 0, sizeof(sum));
int ans = 0;
for(int i = 0; i < n; i ++){
for(int j = 0; j < m; j ++){
cin >> a[i][j];
sum[i] += a[i][j];//每行矩陣和
ans += a[i][j];
}
}
if(k >= min(n, m)){
cout << ans << endl;
return;
}
ans = 0;
for(int t = 0; t < (1 << n); t ++){
int cnt = 0, res = 0;
for(int i = 0; i < n; i ++) cnt += (t>>i)&1;//二進制1的個數
if(k - cnt < 0 || k - cnt > m) continue;//留給列的次數
memset(tmp, 0, sizeof(tmp));
for(int i = 0; i < n; i ++){
if((t>>i)&1) res += sum[i]; //該行消去
else for(int j = 0; j < m; j ++) tmp[j] += a[i][j]; //該列保留
}
sort(tmp, tmp + m, greater<int>());//從大到小排序
for(int i = 0; i < k - cnt; i ++) res += tmp[i];
ans = max(ans, res);
}
cout << ans << endl;
}
int main(){
io;
solve();
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/264746.html
標籤：其他
上一篇：Js練習1：收集垃圾。