题目

题目描述:
一种新型的激光炸弹,可以摧毁一个边长为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;
}
//函数区