51nod 1625 夹克爷发红包（状压枚举+贪心）

1625 夹克爷发红包 基准时间限制：1 秒 空间限制：131072 KB 分值: 20  难度：3级算法题  收藏  关注 在公司年会上，做为互联网巨头51nod掌门人的夹克老爷当然不会放过任何发红包的机会。 现场有n排m列观众，夹克老爷会为每一名观众送出普通现金红包，每个红包内金额随机。 接下来，夹克老爷又送出 最多k组高级红包，每 组高级红包会同时给一排或一列的人派发 ,每 个高级红包的金额皆为x。 派发高级红包时，普通红包将会强制收回。同时，每个人只能得到一个高级红包。（好小气！） 现在求一种派发高级红包的策略，使得现场观众获得的红包总金额最大。 Input 第一行为n, m, x, k四个整数。 1 <= n <= 10, 1 <= m <= 200 1 <= x <= 10^9，0 <= k <= n + m 接下来为一个n * m的矩阵，代表每个观众获得的普通红包的金额。普通红包的金额取值范围为1 <= y <= 10^9 Output 输出一个整数，代表现场观众能获得的最大红包总金额 Input示例 3 4 1 5 10 5 7 2 10 5 10 8 3 9 5 4 Output示例 78

思路：这题之前想的是， 将每行每列原来的总和处理出来，然后贪心找，找到在所有行列中与全变成x差值最大的， 找到后把他变成全x， 相应的其他行也变了，再排序，再贪心。。结果只过了一半样例， 这里就有个问题， 如果有两个差值相同呢， 你改哪一个呢？ 改哪一个对后面的结局都会有影响， 这应该就是错误地方了把。。先放错误代码：

#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int maxn = 3e2 + 5; typedef long long ll; struct node { ll val, id; }precol[maxn], prerow[maxn]; int a[maxn][maxn]; int cmp(node a, node b) { return a.val < b.val; } int main() { ll n, m, x, k; while(~scanf("%lld%lld%lld%lld", &n, &m, &x, &k)) { ll ans = 0; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) scanf("%d", &a[i][j]), prerow[i].val = prerow[i].val + a[i][j], prerow[i].id = i, ans += a[i][j]; // cout << ans << endl; for(int i = 1; i <= m; i++) for(int j = 1; j <= n; j++) precol[i].val = precol[i].val + a[j][i], precol[i].id = i; while(k--) { sort(precol+1, precol+m+1, cmp); sort(prerow+1, prerow+n+1, cmp); if(x*n-precol[1].val > x*m-prerow[1].val) //如果相同，无法抉择选哪一个 { if(x*n-precol[1].val <= 0) continue; ans += x*n-precol[1].val; for(int i = 1; i <= n; i++) prerow[i].val -= (a[i][precol[1].id] + x), a[i][precol[1].id] = x; } else { if(x*m-prerow[1].val <= 0) continue; ans += x*m-prerow[1].val; for(int i = 1; i <= m; i++) precol[i].val -= (a[prerow[1].id][i] + x), a[prerow[1].id][i] = x; } } printf("%lld\n", ans); } return 0; }

正确的思路： 做题一定要读题一定要读题， 你发现n才10，为什么m200， n才10呢。。正解是，枚举所有行的可能性，一共1<<n = 1024种方案，正解取那几行肯定也在这里面，取某几行，肯定这几行就都是x了， 然后贪心找最小的列就好了，注意，这里先取行，跟先取列没有区别， 注意要在k组之内~

总结下， 这里就是枚举所有可能性，肯定有一种在答案里，这里行列顺序没关系， 都是把那几个数变成x，所以顺序根本没关系， 找出行所有可能性， 列中肯定越少越好，这种思想，把答案可以由两种东西组合在一起，他分开考虑了，放在一起考虑会相互羁绊， 如果我确定一种，另一种就可以根据自己性质搞事了，也就是可以一个维度枚举，一个维度用贪心算法。这种思想要学习。

#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; typedef long long ll; const int maxn = 205; int a[maxn][maxn]; int n, m, k; ll x, precol[maxn], prerow[maxn]; int main() { while(~scanf("%d%d%lld%d", &n, &m, &x, &k)) { for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) scanf("%d", &a[i][j]), prerow[i] = prerow[i] + a[i][j]; ll ans = 0; for(int s = 0; s < (1<<n); s++) { int cnt = 0; ll temp = 0; memset(precol, 0, sizeof(precol)); for(int j = 0; j < n; j++) { if((1<<j)&s) { cnt++; temp = temp + m*x; } else temp = temp + prerow[j]; } // cout << temp << endl; if(cnt > k) continue; for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { int z = (1<<j)&s ? x : a[j][i]; precol[i] = precol[i] + z; } } sort(precol, precol+m); int t = k - cnt; for(int l = 0; l < min(m,t); l++) { // if(s == 0) cout << precol[l] << endl; if(x*n > precol[l]) //如果不划算，不要换 temp = temp - precol[l] + n*x; } // cout << temp << endl; // if(temp > ans) cout << s << endl; ans = max(ans, temp); } printf("%lld\n", ans); } return 0; }