激光炸弹——二维前缀和

基本概念——一维前缀和

对于一个原始序列$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);
    }
}