《算法竞赛进阶指南》[HNOI2003]激光炸弹--题解

题目描述
一种新型的激光炸弹，可以摧毁一个边长为R的正方形内的所有的目标。
现在地图上有n(N ≤ 10000)个目标，用整数Xi,Yi(其值在[0,5000])表示目标在地图上的位置，每个目标都有一个价值。
激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆破范围，即那个边长为R的正方形的边必须和x，y轴平行。
若目标位于爆破正方形的边上，该目标将不会被摧毁。

输入描述:
输入文件的第一行为正整数n和正整数R，接下来的n行每行有3个正整数，分别表示 xi，yi ，vi 。

输出描述:
输出文件仅有一个正整数，表示一颗炸弹最多能炸掉地图上总价值为多少的目标（结果不会超过32767）。

前缀和：
其实可以把它理解为数学上的数列的前n项和（对于一个一维数组的前缀和）。
我们定义对于一个数组a的前缀和数组s，s[i] = a[1]+a[2]+...+a[i].

二维前缀和：
与一维前缀和类似，设s[i][j]表示所有a[i'][j']的和。（1≤i'≤i,1≤j'≤j）
有一点像“矩形的面积”那样，把一整块区域的值都加起来。

当给出一个数列s，要求你回答m次询问，每次询问下标j到k(k > j)的和。怎么算更快呢？暴力发就是每次询问都执行一次相加操作，然后输出结果。
可是这样算会TLE的。可以先提前算好每一次的前缀和，再用s[k]-s[j],这样便会使计算量大大减小。

(图片来源于网络)

假设在这个矩阵（二维数组）中，我们要求和的是上图中红区。现在我们已经预处理出了所有点的前缀和，现在给定两个点（x1,y1），（x2,y2），我们要求 以这两个点连线为对角线的一个子矩阵的数值之和。

首先我们可以把s[x2][y2]求出来，它代表整个大矩形的前缀和，然后我们分别减去它左边多出来的一块的前缀和和下边多出来一块的前缀和。
最后可以发现绿色部分多剪了一次，加回来，就ok了。
所以对于一次的查询答案ans应该等于 。

废话少说直接上代码：

完整C++版AC代码：

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

const int N = 5010;//这个N表示点最多的数量
int g[N][N];

int main() {

    int N, R;//为了方便就重名了，两个N重名是没关系的，因为会优先选择函数里的
    cin >> N >> R;
    int xx = R, yy = R;//xx和yy表示边界，初始化为最小的R

    for (int i = 0,x,y,w; i < N; ++i) {
        cin >> x >> y >> w;
        x++; y++;//坐标x，y都要加1，因为这道题目的坐标是从0开始的
        g[x][y] = w;
        xx = max(xx, x);
        yy = max(yy, y);
    }

    for (int i = 1; i <= xx; i++) 
        for (int j = 1; j <= yy; j++)
            g[i][j] = g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1] + g[i][j];//求前缀和

    int ans = 0;
    for (int i = R; i <= xx; i++) {
        for (int j = R; j <= yy; j++) {
            ans = max(ans, g[i][j] - g[i - R][j] - g[i][j - R] + g[i - R][j - R]);//用提前算好的前缀和减去其他部分再补上多剪的那部分
        }
    }
    printf("%d\n", ans);
    return 0;
}