CF446B DZY Loves Modification

本文主要是介绍CF446B DZY Loves Modification，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题面：CF446B DZY Loves Modification

题意：

\(zyb\) 有一个 \(n \times m\) 的矩阵，他每次选某一行或者某一列，使自己的快乐值加上这一行/列的总和。之后这一行/列的所有数字大小减去 \(p\) 。问 \(k\) 次操作之后最大快乐值为多少。

解法：

由于某一行的更改不会影响其他行的答案，某一列的更改不会影响其他列的答案，所以我们单独考虑行和列。

令 \(sum_1[i]\) 表示单独操作行 \(i\) 次能得到的最大快乐值，\(sum_2[i]\) 表示单独操作列 \(i\) 次能得到地最大快乐值。所以答案就是 \(\max\) {\(sum_1[i] + sum_2[k-i]+p \cdot i \cdot(k-i)\)}。

预处理 \(sum_1\) 和 \(sum_2\) 两个数组就用优先队列，不多解释。

至于减 \(p \cdot i \cdot(k-i)\) ，可以考虑成 \(i\) 条行线和 \((k - i)\) 条列线的交点个数。（这个手玩小样例也能发现）

时间复杂度：

\(O(k \log n)\) 。

Code

这篇关于CF446B DZY Loves Modification的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

C/C++教程