思路:
先枚举行,在确定行的基础上去贪心列。
用01字符串去枚举,这个还是头会见,毕竟菜的扣脚。
思路不是很难懂。
#include<iostream> #include<string> #include<math.h> #include<algorithm> #include<vector> //#include<bits/stdc++.h> typedef long long ll; ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } ll lcm(ll a, ll b) { return a * b / (gcd(a, b)); } #define PII pair<int,int> using namespace std; const int N = 2e6 + 10, mod = 1e9 + 7; int qmi(int a, int k, int p) //快速幂模板 { int res = 1; while (k) { if (k & 1) res = (ll)res * a % p; k >>= 1; a = (ll)a * a % p; } return res; } /////////////////////////////////////////////////////////// int n, m, k,an[25][25]; long long he[25], sumlie[25],ans = 0; bool b[25]; int solve(int x) { memset(b, 0, sizeof(b)); int answer = 0, i = 1; while (x) { if (x & 1) //末尾为1 { answer++; b[i] = 1; } x >>= 1; i++; } return answer; } int main() { cin >> n >> m >> k; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { cin >> an[i][j]; he[i] += an[i][j]; } if (k > n || k > m) k = max(n, m); int tmp = (1 << n) - 1; for (int t = 0; t <= tmp; t++) { int hang = solve(t); int lie = k - hang; if (lie > m || lie < 0) continue; long long sum = 0; for (int i = 1; i <= n; i++) if (b[i]) sum += he[i]; memset(sumlie, 0, sizeof(sumlie)); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (b[i]==0) sumlie[j] += an[i][j]; sort(sumlie + 1, sumlie + 1 + m); for (int i = 1, j = m; i <= lie; i++, j--) sum += sumlie[j]; //直接贪心处理 ans = max(ans, sum); } cout << ans << endl; return 0; }