可以摧毁一个包含 R×R 个位置的正方形内的所有目标 ==> 只能摧毁正方形内部的格点
假设正方形的边长为r,如果正方形放在边界,此时正方形可以覆盖(r + 1)^2个点,因为长度为1的线段需要两
个点来组成,长度为n需要n + 1个点组成。
边长为3时,如果正方形放在边界上,如下图所示,最多可以炸掉4个点
如果正方形的四个顶点不放在边界上,则可以炸掉r^2个点,如下图所示。
下面考虑将格点的值转移到格子中,注意转移后的坐标应看在格子上而非格点!
对于值在格点上时,可以考虑将格点上的值放到格子中,把每个格点上的值都放到右下角的格子中,如上图中
的小红点。图中A点(4, 4)为正方形放在边界上时的右下点。所以当右下角为A时可以炸掉的最大值的情况,值
由格点转化到格子中时,考虑的右下角下标不变,可以炸掉的左上角(2, 2)向格子移动变成(2, 2)。
公示中的左上点x - 1 即 2 - 1 = 1 即 右下角坐标的x - 长度r
注意
不论是格点还是格子都是用点表示的,转化为格子后点2就代表第二个格子,而不是1~2这个范围。
二维前缀和中,值虽然在格子中,但是用点表示的格子!!
总结
看上面的过程,将格点的值转移到格子中貌似就是将三个点转化成三个格子,但是r是不变的,所以起初的三个
点的实际长度只有2,而无论是格点还是格子,都是用点来表示的,所以转化为三个格子后它的长度应该是3,
实际上还是2,所以左端点的值为R - 实际长度(2),但已有长度是3,所以左端点的值就是R - 3 + 1,所以最
后不用在减去1。
代码
#include "bits/stdc++.h"
using namespace std;
const int N = 5e3 + 10;
int n, m; // n和m分别为棋盘的最大右下角坐标
int s[N][N];
int main()
{
int cnt, R;
cin >> cnt >> R;
// 5001是考虑到所有的xy坐标都加一 同时保证下面枚举的坐标轴中可以放的下r * r的正方形
R = min(R, 5001);
// 待会枚举右下角
n = m = R;
while (cnt--)
{
int x, y, w;
cin >> x >> y >> w;
x++, y++;
n = max(n, x), m = max(m, y);
s[x][y] += w;
}
// 预处理前缀和
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + s[i][j];
// 求答案
int ans = 0;
for (int i = R; i <= n; i++)
for (int j = R; j <= m; j++)
// 画图可以理解为什么直接-R不需要在额外-1
// 如果当前在3 R为2 则左x为3 - 2 + 1 = 2 要减去1处就是直接-R处的点
ans = max(ans, s[i][j] - s[i - R][j] - s[i][j - R] + s[i - R][j - R]);
cout << ans;
return 0;
}