首先要知道选择行列操作时顺序是无关的
用两个数组row[i],col[j]分别表示仅选择i行能得到的最大值和仅选择j列能得到的最大值
这个用优先队列维护，没选择一行(列)后将这行(列)的和减去相应的np (mp)重新加入队列
枚举选择行的次数为i,那么选择列的次数为k - i次，ans = row[i] + col[k - i] - (k - i) * i * p;
既然顺序无关，可以看做先选择完i次行，那么每次选择一列时都要减去i * p，选择k - i次列，即减去(k - i) * i * p
//#pragma comment(linker, /stack:102400000,102400000)//head#include #include #include #include #include #include #include #include #include #include #include #include using namespace std;//loop#define fe(i, a, b) for(int i = (a); i = (a); --i)#define rep(i, n) for(int i = 0; i = (a); --i)#define cpy(a, b) memcpy(a, b, sizeof(a))#define fc(it, c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); it++)#define eq(a, b) (fabs((a) - (b)) vi;typedef unsigned long long ull;typedef long long ll;const int inf = 0x3f3f3f3f;const int maxn = 1010;const double eps = 1e-10;const ll mod = 1e9 + 7;int ipt[maxn][maxn];ll row[maxn * maxn], col[maxn * maxn];ll rtol[maxn], ctol[maxn];int main(){ int n, m, k, p; while (~riv(n, m, k, p)) { priority_queue r, c; int radd = 0, cadd = 0; clr(rtol, 0), clr(ctol, 0); fe(i, 1, n) fe(j, 1, m) { ri(ipt[i][j]); rtol[i] += ipt[i][j]; ctol[j] += ipt[i][j]; } fe(i, 1, n) r.push(rtol[i]); fe(j, 1, m) c.push(ctol[j]); row[0] = 0, col[0] = 0; fe(i, 1, k) { ll x = r.top(), y = c.top(); r.pop(), c.pop(); r.push(x - m * p); c.push(y - n * p); row[i] = row[i - 1] + x; col[i] = col[i - 1] + y; }// fe(i, 0, k)// cout