技巧:
二维前缀和 + 枚举
思路:
求出坐标轴的二维前缀和, 然后按照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)
} 
京公网安备 11010502036488号