题目

地图上有 $N$ 个目标，用整数 $X_i,Y_i$ 表示目标在地图上的位置，每个目标都有一个价值 $W_i$。

注意：不同目标可能在同一位置。

现在有一种新型的激光炸弹，可以摧毁一个包含 $R\times R$ 个位置的正方形内的所有目标。

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

若目标位于爆破正方形的边上，该目标不会被摧毁。

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

输入格式

第一行输入正整数 $N$ 和 $R$，分别代表地图上的目标数目和正方形的边长，数据用空格隔开。

接下来 $N$ 行，每行输入一组数据，每组数据包括三个整数 $X_i,Y_i,W_i$，分别代表目标的 $x$ 坐标，$y$ 坐标和价值，数据用空格隔开。

输出格式

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

数据范围

• $0\le R\le 10^9$
• $0<N\le 10000$
• $0\le X_i,Y_i\le 5000$
• $0\le W_i\le 1000$

输入样例

2 1
0 0 1
1 1 1

输出样例

1

分析

因为 $X_i,Y_i$ 的值在 0 ~ 5000 之间，所以可以建立一个二维数组 $A$，其中，$A[i][j]$ 就等于位置 $(i,j)$ 上的所有目标的价值之和。即对于每个目标，令 $A[X_i][Y_i]+=W_i$。

接下来求出 $A$ 的二维前缀和 $S$，即：
$$S[i][j]=\sum _{x=1}^i\sum _{y=1}^{j}A[x][y]$$
如下图所示，再观察 $S[i][j]，S[i-1][j]，S[i][j-1]，S[i-1][j-1]$ 的关系。

容易得到如下的递推式：
$$S[i][j]=S[i-1][j]+S[i][j-1]-S[i-1][j-1]+A[i][j]$$

同理，对于任意一个边长为 $R$ 的正方形，有：
$$\sum _{x=i-R+1}^i\sum _{y=j-R+1}^{j}A[x][y]=S[i][j]-S[i-R][j]-S[i,j-R]+S[i-R][j-R]$$

因此，只需要 $O(N^2)$ 递推求出二维前缀和 $S$，然后 $O(N^2)$ 枚举边长为 $R$ 的正方形的右下角坐标 $(i,j)$，即可通过上式 $O(1)$ 计算出该正方形内所有目标的价值之和，更新答案。上面给出的两个式子蕴含的思想其实就是 “容斥原理”。

值得一提的是，上面将 $(X_i,Y_i)$ 作为一个“格子”，而原题中 $(X_i,Y_i)$ 是一个点，并且正方形边上的目标不会被摧毁。实际上，不妨认为这个点就处于 “格子” $(X_i,Y_i)$ 的中心位置，格子的左上角坐标为 $(X_i-0.5,Y_i-0.5)$，右下角坐标为 $(X_i+0.5,Y_i+0.5)$，而正方形的右下角处于 “格线交点” 上，即一个值为 “□.5” 的坐标。这个转化与原问题是等价的。另外，本题内存限制较为严格，可以省略 $A$ 数组，读入时直接向 $S$ 中累加。

代码

#include <iostream>
using namespace std;const int N = 5010;int S[N][N]; //前缀和数组int main() {int N; //目标数 或者说 点数int R;cin >> N >> R;R = min(R, 5001); for (int i = 0, x, y, w; i < N; i++) {cin >> x >> y >> w;//为防越界，下标从1开始S[x + 1][y + 1] += w;}//求二维前缀和for (int i = 1; i <= 5001; i++) {for (int j = 1; j <= 5001; j++) {S[i][j] += S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1]; }}//枚举边长为R的正方形int res = 0;for (int i = R; i <= 5001; i++) {for (int j = R; j <= 5001; j++) {//因为在正方形边上的不能爆破，所以实质上计算的是边长为R-1的正方形res = max(res, S[i][j] - S[i - R][j] - S[i][j - R] + S[i - R][j - R]); }}cout << res << endl;return 0;
}