技巧:
二维前缀和 + 枚举
思路:
求出坐标轴的二维前缀和, 然后按照R边长枚举结果更新答案
实现:
package main import "fmt" var m = make([][5001]int, 5001) var sumArr = make([][5001]int, 5001) var ans = 0 func main() { var n, R int fmt.Scan(&n, &R) for i := 0; i < n; i ++ { var x, y, v int fmt.Scan(&x, &y, &v) m[x][y] = v } // 构建二维前缀和 for row := 0; row < 5001; row ++ { for col := 0; col < 5001; col ++ { if row == 0 && col == 0 { sumArr[row][col] = m[row][col] }else if col == 0 { sumArr[row][col] = sumArr[row - 1][col] + m[row][col] }else if row == 0 { sumArr[row][col] = sumArr[row][col - 1] + m[row][col] }else { sumArr[row][col] = sumArr[row - 1][col] + sumArr[row][col - 1] - sumArr[row - 1][col - 1] + m[row][col] } } } // 枚举炮弹覆盖区域 for i := R - 1; i < 5001; i ++ { for j := R - 1; j < 5001; j ++ { rangeValue := sumArr[i][j] if i - R > 0 && j - R > 0 { rangeValue = rangeValue - sumArr[i - R][j] - sumArr[i][j - R] + sumArr[i - R][j - R] }else if i - R > 0 { rangeValue -= sumArr[i - R][j] }else if j - R > 0 { rangeValue -= sumArr[i][j - R] } if rangeValue > ans { ans = rangeValue } } } fmt.Println(ans) }