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)$列,减去重复部分,取最大值,即可得到答案。
代码
1 |
|
DZY Loves Modification
https://regmsif.cf/2017/07/20/oi/dzy-loves-modification/