题目

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

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

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

解析

这道题看到的时候，我虎躯一震，写过差不多的！就可以直接二维前缀和。
  • 我不会乱说是因为我到现在还不会线段树的orzzzz


先看题吧：
  • 题目告诉我们：我们已知了爆破的正方形边长，要求可以爆破的最大值。


首先是我们的暴力灵感：
  • 我们将左上角点代表方阵，然后计算方阵里面的值，遍历一圈然后选最大值就好，不过超时是肯定的。


巨巨曾经说过：我们写代码要从会暴力开始提升境界，然后我们来想一下怎么优美的暴力：
  1. 我们上面讲到了，我们可以用一个顶点代替一个方阵。但是我们上面是用了遍历这个方阵，我们何不真用这个点代替方阵呢！
  2. 什么叫真的代替方阵！就是前缀和呀！！！我们这个二维前缀和储存：以原点和该点为对角线的矩形内的数字之和。
  3. 也就是说，我们在判断某一个点时，就能知道他所代表的矩形的值（计算怎么办，下面会讲）。
  4. 这就是这里二维前缀和的基本思路了。


那么这个前缀和怎么构造呢？
  • 其实很简单，知道递推式我们很简单就能得到了： 
    sum[i][j] = mp[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
//某一点的前缀和 = 该点值 + 上面一点的前缀和 + 左边一点的前缀和 - 上边和左边重叠的部分
    虽然很好理解，但我还是画了个图：


那这个前缀和该怎么运算呢？怎么弄成方阵呢？
  1. 我们还是和上面一样，先看图：
  2. 从图里面我们还是发现，得到某一个方阵的方法是去掉左边和上面的区间，在加上重合的区间。
    不过要注意这里是k*k，所以减去的应该是 i - k 和 j - k 的位置的矩形。
  3. 所以我们判断的公式应该是： 
    sum[x][y] - sum[x - k][y] - sum[x][y - k] + sum[x - k][y - k]


打代码咯：
  1. 所以我们先讲原来的矩阵保存下来。
  2. 然后初始化前缀和（详情看上方小专栏）。
  3. 随后我们就可以判断方阵递推啦。
  4. 详情看代码趴~

AC代码 

#include <iostream>
#include <algorithm>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区

const int MAX = 5e3 + 7;
int sum[MAX][MAX];
//全局变量区

int calc(int i, int j, int r) { 
    return sum[i][j] - sum[i - r][j] - sum[i][j - r] + sum[i - r][j - r];
}
//函数预定义区

int main() {
    IOS;
    int n, r; cin >> n >> r;
    for (int i = 1; i <= n; i++) {
        int x, y, val; cin >> x >> y >> val;
        sum[x + 1][y + 1] = val;
    }
    for (int i = 1; i <= 5e3; i++)
        for (int j = 1; j <= 5e3; j++)
            sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
    int ans = 0;
    for (int i = r; i <= 5e3; i++)
        for (int j = r; j <= 5e3; j++)
            ans = max(ans, calc(i, j, r));
    cout << ans << endl;
    return 0;
}
//函数区