建站套餐,做视频网站软件有哪些,手表购物网站排名,购物网站建设目标Problem: AcWing 99. 激光炸弹 文章目录 思路解题方法复杂度Code 思路 这是一个二维前缀和的问题。我们需要找到一个r*r的方格#xff0c;使得这个方格内的所有点的权值和最大。我们可以先计算出每个点的前缀和#xff0c;然后枚举每个可能的方格#xff0c;计算出这个方格内… 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;}}
