[数据结构与算法]99. 激光炸弹 java 题解 （前缀和）

输入样例：

2 1
0 0 1
1 1 1

输出样例：

1

解题思路：

先求出二维数组的前缀和数组，在这个数组上找满足条件的最大子矩阵的权值。

Java代码：

import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] split = br.readLine().split(" ");
		int n = Integer.parseInt(split[0]);
		int r = Integer.parseInt(split[1]);
		int [][]arr = new int[5002][5002];
		long [][]s = new long[5002][5002];
		int m = 5001;
		for(int i = 0; i < n; i++) {
			split = br.readLine().split(" ");
			int x = Integer.parseInt(split[0]) + 1;
			int y = Integer.parseInt(split[1]) + 1;
			int w = Integer.parseInt(split[2]);
			arr[x][y] += w;//权值可以累加
		} 
		
		for(int i = 1; i <= m; i++) {//求前缀和
			for(int j = 1; j <= m; j++) {
				s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + arr[i][j];//也可以直接原数组上操作在
			}
		}
		
		r = Math.min(r, m);//当正方形边长远大于数组长度时，特判
		
		long max = 0;
		for(int i = 1; i <= m - r + 1; i++) {
			for(int j = 1; j <= m - r + 1; j++) {
				int x1 = i, y1 = j;
				int x2 = x1 + r - 1, y2 = y1 + r - 1;//划分正方形区域
				long sum = s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];
				if(max < sum) max = sum;
			}
		}
		System.out.println(max);
	}
}

?

?