题目链接：这里 题意： 有一个n*m的矩阵，你需要操作k次，每次操作是选择一行或者一列，使得ans+=这一行或者这一列的和 然后再使得这一行或者这一列的数全部减去p 现在问你他操作k次之后，最多获得多少分数
解法： 假设你最后操作了k次，那么对于整体的答案，你需要减去i*(k-i)*p这么多(重复的点) 这样我们就把p给处理出来了 现在我们再把行和列都分开，然后用一个优先队列去处理就好了 然后这道题就结束了……
//490 E #include <bits/stdc++.h> using namespace std; const int maxn = 1100; long long dp1[maxn*maxn], dp2[maxn*maxn], row[maxn*maxn], col[maxn*maxn], a[maxn][maxn]; priority_queue <long long> q1, q2; int n, m, k;long long p; int main() { scanf("%d%d%d%I64d", &n, &m, &k, &p); for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ scanf("%Id", &a[i][j]); row[i] += a[i][j]; col[j] += a[i][j]; } } while(!q1.empty()) q1.pop(); while(!q2.empty()) q2.pop(); for(int i = 0; i < n; i++) q1.push(row[i]); for(int i = 0; i < m; i++) q2.push(col[i]); dp1[0] = dp2[0] = 0; for(int i = 1; i <= k; i++){ long long x1 = q1.top(); q1.pop(); long long x2 = q2.top(); q2.pop(); dp1[i] = dp1[i-1] + x1; dp2[i] = dp2[i-1] + x2; q1.push(x1 - 1LL*p*m); q2.push(x2 - 1LL*p*n); } long long ans = dp1[0] + dp2[k]; for(int i = 1; i <= k; i++){ ans = max(ans, dp1[i] + dp2[k-i] - 1LL*i*(k-i)*p); } printf("%I64d\n", ans); return 0; }