激光炸弹 —— 二维前缀和

基本概念 —— 一维前缀和

对于一个原始序列 $a [1],a [2],...,a [n]$，其一维前缀和数组为 $s [1],s [2],...,s [n]$

他们之间的关系为：

s[1] = a[1]
s[2] = s[1] + a[2]
s[3] = s[2] + a[3]
......
s[n] = s[n - 1] + a[n]

二维前缀和

假设在一个二维平面上，每个点具有一定的权值，我们要计算点 $(2,2)$ 到 $(8,4)$ 的权值和
首先我们要找到这么几块的面积。所要求的黄色区域，就是黑色 - 绿色 - 粉色 + 青色

对于这题来说，首先打表前缀和，map[i][j] 表示以 $i,j$ 为结尾的前缀和，则有

map[i][j] = map[i][j] + map[i - 1][j] + map[i][j - 1] - map[i - 1][j - 1]

然后两重循环从 $(r,r)$ 开始寻找最大的区间和，因为这道题说，如果某个目标在炸弹的边界上，不会被摧毁，因此我们可以把这个炸弹看成是爆炸范围为 r-1 的正方形

题目数据给出 $x,y$ 都是从 0 开始，但是我们处理数据都是从 1 开始，所以我们对于输入的 $x,y$ 都加 1

import java.util.Scanner;
public class Main {
    static int[][] map = new int[5010][5010];
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int N = cin.nextInt();
        int R = cin.nextInt();
        int n = R, m = R;
        for (int i = 0, x, y, w; i < N; i++) {
            x = cin.nextInt();
            y = cin.nextInt();
            w = cin.nextInt();
            x++; y++;
            n = Math.max(n, x);
            m = Math.max(m, y);
            map[x][y] = w;
        }
        // 处理前缀和
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                map[i][j] += map[i - 1][j] + map[i][j - 1] - map[i - 1][j - 1];
                
        int res = Integer.MIN_VALUE;
        for (int i = R; i <= n; i++)
            for (int j = R; j <= m; j++)
                res = Math.max(res, map[i][j] - map[i - R][j] - map[i][j - R] + map[i - R][j - R]);
        System.out.println(res);
    }
}