AcWing 99. 激光炸弹

Problem: AcWing 99. 激光炸弹

文章目录

• 思路
• 解题方法
• 复杂度
• Code

思路

这是一个二维前缀和的问题。我们需要找到一个r*r的方格，使得这个方格内的所有点的权值和最大。我们可以先计算出每个点的前缀和，然后枚举每个可能的方格，计算出这个方格内的所有点的权值和，取最大值。

解题方法

首先，我们读入所有的点，对于每个点，我们将其权值加到对应的位置上。
然后，我们计算出每个点的前缀和。对于每个点(i, j)，其前缀和等于它左边的点的前缀和加上它上面的点的前缀和，再减去它左上角的点的前缀和，再加上它自己的权值。
最后，我们枚举每个可能的方格，计算出这个方格内的所有点的权值和，取最大值。对于每个方格，其内部所有点的权值和等于右下角的点的前缀和减去左下角的点的前缀和，再减去右上角的点的前缀和，再加上左上角的点的前缀和。

复杂度

时间复杂度:

O ( n 2 ) O(n^2) O(n2)，我们需要枚举每个可能的方格，每个方格的计算复杂度为 O ( 1 ) O(1) O(1)，所以总的时间复杂度为 O ( n 2 ) O(n^2) O(n2)。

空间复杂度:

O ( n 2 ) O(n^2) O(n2)，我们需要存储每个点的前缀和，所以空间复杂度为 O ( n 2 ) O(n^2) O(n2)。

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

public class Main {
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
	static StreamTokenizer sr = new StreamTokenizer(in);
	static int MAXN = 5010;
	static int[][] arr = new int[MAXN][MAXN];
	static int n, r;

	public static void main(String[] args) throws IOException {
		n = nextInt();
		r = nextInt();
		int m = 5001;
		for (int i = 0, x, y, w; i < n; i++) {
			x = nextInt() + 1;
			y = nextInt() + 1;
			w = nextInt();
			arr[x][y] += w;
		}
		// 计算出前缀和
		for (int i = 1; i <= m; i++) {
			for (int j = 1; j <= m; j++) {
				arr[i][j] += arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1];
			}
		}
		// 枚举每个长宽为r的方格总w值
		long ans = 0;
		r = Math.min(r, m);
		for (int a = 1; a <= m - (r - 1); a++) {
			for (int b = 1; b <= m - (r - 1); b++) {
				int c = a + r - 1;
				int d = b + r - 1;
				ans = Math.max(ans, arr[c][d] - arr[a - 1][d] - arr[c][b - 1]
						+ arr[a - 1][b - 1]);
			}
		}
		out.println(ans);
		out.flush();

	}

	private static int nextInt() throws IOException {
		sr.nextToken();
		return (int) sr.nval;
	}

}