輸入樣例：

2 1 0 0 1 1 1 1

輸出樣例：

1

---

解題思路：

先求出二維數(shù)組的前綴和數(shù)組，在這個(gè)數(shù)組上找滿足條件的最大子矩陣的權(quán)值。

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;//權(quán)值可以累加} 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];//也可以直接原數(shù)組上操作在}}r = Math.min(r, m);//當(dāng)正方形邊長遠(yuǎn)大于數(shù)組長度時(shí)，特判l(wèi)ong 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;//劃分正方形區(qū)域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);} }

?

?

總結(jié)

以上是生活随笔為你收集整理的99. 激光炸弹 java 题解 （前缀和）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。