题目描述

地图上有 N 个目标，用整数Xi,Yi表示目标在地图上的位置，每个目标都有一个价值Wi

。

注意：不同目标可能在同一位置。
若目标位于爆破正方形的边上，该目标不会被摧毁。

现在有一种新型的激光炸弹，可以摧毁一个包含 R×R

个位置的正方形内的所有目标。

激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆炸范围，即那个正方形的边必须和x，y

轴平行。

求一颗炸弹最多能炸掉地图上总价值为多少的目标。
输入格式

第一行输入正整数 N
和 R

,分别代表地图上的目标数目和正方形的边长，数据用空格隔开。

接下来N
行，每行输入一组数据，每组数据包括三个整数Xi,Yi,Wi,分别代表目标的x坐标，y

坐标和价值，数据用空格隔开。
输出格式

输出一个正整数，代表一颗炸弹最多能炸掉地图上目标的总价值数目。
数据范围

0≤R≤109

0<N≤10000,
0≤Xi,Yi≤5000
0≤Wi≤1000

样例

输入样例：

2 1
0 0 1
1 1 1

输出样例：

1

算法1

两个重点 ：若目标位于爆破正方形的边上，该目标不会被摧毁。
那个正方形的边必须和x，y轴平行。

若目标位于爆破正方形的边上，该目标不会被摧毁:题上说的意思是一个格子放一个目标，其实就是一个点（x-0.5,y-0.5）,所以目标不可能在边上
看代码吧

时间复复杂度O(n*n)

C++ 代码

#include<iostream>
#include<cstdio>
using namespace std;
int f[5005][5005];
int N, n, m, R, x, y, w;
int main() {
    std::ios::sync_with_stdio(false);
    cin >> N >> R;
    n = R, m = R;//防止在R>n||R>m时求每个点对应的边长为R的正方形的权值时出现错误
    for (int i = 0; i < N; ++i) {
        cin >> x >> y >> w;
        x++, y++; //这个题输入的时候从0开始的，防止数组越界，让坐标从1开始
        f[x][y] = w+f[x][y];//新更新的，若有两个目标放在同一个位置上要叠加
        n = max(n, x), m = max(m, y);//目标所在的最大的横坐标，纵坐标
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
           //每个点对应的那个矩形的权值
            f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + f[i][j];
        }
    }
    int s = 0;
    for (int i = R; i <= n; ++i) {
        for (int j = R; j <= m; ++j) {
   //求出每个点对应的边长为R的正方形的权值进行比较大小
            s = max(s, f[i][j]-f[i - R][j] - f[i][j - R] + f[i - R][j - R]);
        }

    }
    cout << s << endl;
    return 0;
}