hexo-blog/source/_posts/oi/dzy-loves-modification.md

---

title: DZY Loves Modification tags:

• Greedy
• Priority Queue id: "1228" categories:
• [OI, Common Skill]
• [OI, Data Structure] date: 2017-07-20 13:55:19 ---

题目描述

As we know, DZY loves playing games. One day DZY decided to play with a $n \times m$ matrix. To be more precise, he decided to modify the matrix with exactly $k$ operations.

Each modification is one of the following:

• Pick some row of the matrix and decrease each element of the row by $p$. This operation brings to DZY the value of pleasure equal to the sum of elements of the row before the decreasing.
• Pick some column of the matrix and decrease each element of the column by $p$. This operation brings to DZY the value of pleasure equal to the sum of elements of the column before the decreasing.

DZY wants to know: what is the largest total value of pleasure he could get after performing exactly $k$ modifications? Please, help him to calculate this value.

题意概述

给定一个$n \times m$的矩阵，每次可以从这个矩阵中选取一行或一列，将这一行或一列的数字之和加到你的分数上，再将这一行或一列上的每个数字减去$p$。共进行$k$次操作，求分数的最大值。

数据范围：$1 \le n, m \le 1000, \ 1 \le k \le 10^6, \ 1 \le p \le 100$。

算法分析

可以发现交换操作顺序对答案没有影响。因此，可以先计算出只取$i$行可以得到的最大值以及只取$j$列可以得到的最大值，根据贪心策略，可以用优先队列维护一行或一列的数字之和。接着枚举取了$i$行，那么也就取了$(k-i)$列，减去重复部分，取最大值，即可得到答案。

代码

#include <iostream>
#include <queue>
using namespace std;
priority_queue<long long> r, c;
long long n, m, k, p, s, t, ans = -1e18, a[1001][1001], rr[1000001], cc[1000001];
int main()
{
  cin >> n >> m >> k >> p;
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j) cin >> a[i][j];
  for (int i = 1; i <= n; ++i) {
    long long s = 0;
    for (int j = 1; j <= m; ++j) s += a[i][j];
    r.push(s);
  }
  for (int j = 1; j <= m; ++j) {
    long long s = 0;
    for (int i = 1; i <= n; ++i) s += a[i][j];
    c.push(s);
  }
  for (int i = 1; i <= k; ++i) {
    long long u = r.top(); r.pop();
    rr[i] = rr[i - 1] + u;
    r.push(u - p * m);
    u = c.top(); c.pop();
    cc[i] = cc[i - 1] + u;
    c.push(u - p * n);
  }
  for (int i = 0; i <= k; ++i) ans = max(ans, rr[i] + cc[k - i] - p * i * (k - i));
  cout << ans << endl;
  return 0;
}