99. 激光炸弹 --前缀和+暴力 + 动态规划

import java.util.Scanner;
class Main {                                    //前缀和
    static final int MAX = 5050;
    static Scanner sc = new Scanner(System.in);        //输入
    static int[][] arr = new int [MAX][MAX];                    //全局变量放在堆里面 而局部变量放在栈里面 如果把数组放在函数里面 会爆栈

    public static void main(String[] args) {
        int N = sc.nextInt();
        int R = sc.nextInt();
        System.out.println(the_max( N, R));
    }

    public static int the_max(int N, int R) {                   //N 是 个数  ，R 是边长

        int X = R;                                      //要大于等于R 避免后面的处理
        int Y = R;                                                                         //外面不一定是正方形
        int ans = 0 ;
        for(int i = 0 ; i < N ; i ++) {
            int p_x = sc.nextInt() + 1;                 
            int p_y = sc.nextInt() + 1;                 //加一为了消除0的边界问题 因为后面有[i-1] 0-1 => error
            arr[p_x][p_y] = sc.nextInt();
            X = Math.max(p_x, X);                       //记录边界
            Y = Math.max(p_y, Y);
        }
        for(int i = 1 ; i <= X ; i++) {
            for(int j = 1 ; j <= Y ; j++) {
                arr[i][j] += arr[i-1][j] + arr[i][j-1] - arr[i-1][j-1];    //动态规划
            }
        }
        for(int i = R ; i <= X ; i++) {                                                //用于在R之间的范围内筛选 
            for(int j = R ; j <= Y ; j++) {
                ans = Math.max(ans,arr[i][j]-arr[i-R][j]-arr[i][j-R]+arr[i-R][j-R]);
            }
        }
        return ans ;
    }
}

import java.util.*;
class Main{
    //为了方便在外面定义一个数组
    static int[][] grid=new int[5011][5011];
    static int maxRow=0,maxCol=0;
    public static void main(String[] args){
        Scanner scan=new Scanner(System.in);
        int N=scan.nextInt();
        int R=scan.nextInt();
        //有可能所有点的坐标都比R小，这样没法弄
        maxRow=R;maxCol=R;
        while(N-->0){
            int x=scan.nextInt()+1;
            int y=scan.nextInt()+1;
            int w=scan.nextInt();
            grid[x][y]+=w;
            maxRow=Math.max(maxRow,x);
            maxCol=Math.max(maxCol,y);
        }
        System.out.println(helper(grid,R));
    }
    static int helper(int[][] grid,int R){
        //构造前缀和矩阵
        for(int r=1;r<=maxRow;r++){
            for(int c=1;c<=maxCol;c++){
                //[r][c]是一个权值，其他三个是已经计算过的前缀和
                grid[r][c]+=grid[r-1][c]+grid[r][c-1]-grid[r-1][c-1];
            }
        }
        int ans=0;
        for(int r=R;r<=maxRow;r++){
            for(int c=R;c<=maxCol;c++){
                //temp是以rc为右下角，边长为R-1的矩阵面积
                int temp=grid[r][c]-grid[r-R][c]-grid[r][c-R]+grid[r-R][c-R];
                ans=Math.max(ans,temp);
            }
        }
        return ans;
    }
}