DZY Loves Modification

题目描述

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;
}

RegMs If

418 I'm a teapot

Leave a Reply

Your email address will not be published. Required fields are marked *