http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1625&judgeId=203076
一开始的时候，还想着枚举每一行的总和，和每一列的总和，然后选一个最小的来变就好。
然后wa了，只剩下一组数据，然后看到还是大数据，调试不了。
然后上网搜，然后跪了。
我那种做法应该是有后效性的。数据在下面
3 3 30 2
10 10 10
1 1 99
20 20 99
不知道怎么描述这种情况，应该就算是一个二维贪心的反例吧。
但是，如果只能改变列，那么是不会存在后效性的。
同时注意到，n的大小是10，可以暴力2^n，枚举每一行时候变化，然后贪心变列。
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> #include <bitset> const int maxn = 200 + 20; LL a[maxn][maxn]; LL b[maxn][maxn]; int n, m, k; LL x; void init() { for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { b[i][j] = a[i][j]; } } } int calc(int val) { //复杂度O("1"的个数) int ans = 0; while (val) { val &= val - 1; ans++; } return ans; } void change(int val) { for (int i = 0; i <= n - 1; ++i) { if ((val & (1 << i)) != 0) { for (int j = 1; j <= m; ++j) { b[i + 1][j] = x; } } } } struct node { LL sum; int id; bool operator < (const struct node & rhs) const { if (sum != rhs.sum) return sum < rhs.sum; else return id < rhs.id; } }c[maxn]; void did(int lef) { //还剩下lef次操作 int lenc = 0; for (int i = 1; i <= m; ++i) { LL sum = 0; for (int j = 1; j <= n; ++j) { sum += b[j][i]; } ++lenc; c[lenc].sum = sum; c[lenc].id = i; } sort(c + 1, c + 1 + lenc); int en = min(lenc, lef); for (int i = 1; i <= en; ++i) { // if (c[i].sum >= x * n) return; for (int j = 1; j <= n; ++j) { b[j][c[i].id] = x; } } } LL now() { LL ans = 0; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { ans += b[i][j]; } } return ans; } void work() { cin >> n >> m >> x >> k; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { cin >> a[i][j]; } } LL ans = 0; int en = (1 << n) - 1; for (int i = 0; i <= en; ++i) { if (calc(i) > k) continue; init(); change(i); did(k - calc(i)); ans = max(ans, now()); } cout << ans << endl; } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif work(); return 0; }
wa的，还要用了BIT的超级复杂的代码
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> #include <bitset> const int maxn = 200 + 20; LL row[maxn][maxn], col[maxn][maxn]; int n, m; int lowbit(int x) { return x & (-x); } void upDate(int which, int id, int pos, LL val) { if (which == 1) { while (pos <= m) { row[id][pos] += val; pos += lowbit(pos); } } else { while (pos <= n) { col[id][pos] += val; pos += lowbit(pos); } } } LL ask(int which, int id, int pos) { LL ans = 0; if (which == 1) { while (pos) { ans += row[id][pos]; pos -= lowbit(pos); } } else { while (pos) { ans += col[id][pos]; pos -= lowbit(pos); } } return ans; } void tochange(int which, int id, LL val) { if (which == 1) { for (int i = 1; i <= m; ++i) { LL now = ask(which, id, i) - ask(which, id, i - 1); upDate(which, id, i, -now); upDate(which, id, i, val); } for (int i = 1; i <= m; ++i) { LL now = ask(2, i, id) - ask(2, i, id - 1); upDate(2, i, id, -now); upDate(2, i, id, val); } } else { for (int i = 1; i <= n; ++i) { LL now = ask(which, id, i) - ask(which, id, i - 1); upDate(which, id, i, -now); upDate(which, id, i, val); } for (int i = 1; i <= n; ++i) { LL now = ask(1, i, id) - ask(1, i, id - 1); upDate(1, i, id, -now); upDate(1, i, id, val); } } } void work() { LL x; int k; cin >> n >> m >> x >> k; // scanf("%d%d%lld%d", &n, &m, &x, &k); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { int t; scanf("%d", &t); upDate(1, i, j, t); upDate(2, j, i, t); } } // tochange(1, 1, 10); // cout << ask(2, 2, n) << endl; for (int i = 1; i <= k; ++i) { LL canadd = 0; int id = 0; for (int j = 1; j <= n; ++j) { LL cango = x * m; LL sum = ask(1, j, m); if (cango > sum && cango - sum > canadd) { canadd = cango - sum; id = j; } } for (int j = 1; j <= m; ++j) { LL cango = x * n; LL sum = ask(2, j, n); if (cango > sum && cango - sum >= canadd) { canadd = cango - sum; id = j + n; } } if (id == 0) break; if (id <= n) { tochange(1, id, x); } else { id -= n; tochange(2, id, x); } } LL ans = 0; for (int i = 1; i <= n; ++i) { ans += ask(1, i, m); } cout << ans << endl; } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif work(); return 0; }