题目内容

塔子哥正在承包月亮市星星区的一片农场。为了提高农场的利润，塔子哥打算选取部分区域引进高级培育技术。已知进行试点的区域的农作物价值计算公式如下：最大利润 = 选中区域中的各地块收入总和 - 区域内地块个数 $\times$ $5$。 整个农场区域是一个矩形区域，被划分为 $n \times m$ 个地块。在进行规划前，农场技术人员对每个地块进行了勘测，计算出每个地块的最大年产量，使用 $n \times m$ 矩阵表示。

为了最大化农场的利润，并降低管理成本，塔子哥打算选择一个矩形区域引进高级培育技术。他想知道，应该选择多少个地块进行引进高级培育技术，以获得最大的年利润。

思路：二维前缀和

给定一个 $n*m$ 的矩阵，矩阵中的每个点，都有一个价值 $a[i][j]$ ，我们需要找到一个价值最大的矩阵，该矩阵的价值为其范围内所有点的价值之和，同时，每包含一个点，就需要减去 $5$ 的价值。

我们很容易想到，在直到矩阵大小后，我们能够 $O(1)$ 的计算出里面有多少个点，但是我们缺少一种方法，一种能够快速求得矩阵内价值总和的方法。

这种方法就是二维前缀和，它能够在 $O(NM)$ 的预处理后， $O(1)$ 获得我们想要的答案。

二位前缀和的原理如下：