题目链接
题目描述
题解：
做一道题，复习一下二维前缀和，设数组
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j]，表示第 i 行第 j 列格子左上部分所有元素的和(包括自己)，
初始化递推公式：
d
p
[
i
]
[
j
]
=
d
p
[
i
−
1
]
[
j
]
+
d
p
[
i
]
[
j
−
1
]
−
d
p
[
i
−
1
]
[
j
−
1
]
+
w
[
i
]
[
j
]
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + w[i][j]
dp[i][j]=dp[i−1][j]+dp[i][j−1]−dp[i−1][j−1]+w[i][j]
查询子区间和(区间左上角格子为(
x
1
,
y
1
x_{1}, y_{1}
x1,y1)，右下角格子坐标为(
x
2
,
y
2
x_{2}, y_{2}
x2,y2))：
a
n
s
=
d
p
[
x
2
]
[
y
2
]
−
d
p
[
x
1
−
1
]
[
y
2
]
−
d
p
[
x
2
]
[
y
1
−
1
]
+
d
p
[
x
1
−
1
]
[
y
1
−
1
]
ans = dp[x_{2}][y_{2}] - dp[x_{1} - 1][y_{2}] - dp[x_{2}][y_{1} - 1] + dp[x_{1} - 1][y_{1} - 1]
ans=dp[x2][y2]−dp[x1−1][y2]−dp[x2][y1−1]+dp[x1−1][y1−1]
回归本题：
初始化前缀和，然后枚举边长为r的子区间即可，注意根据读入数据最大值确定x和y边界大小。
AC代码
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <list>
#include <iomanip>
#include <algorithm>
#include <fstream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std
;
typedef long long ll
;
const int N
= 5e3 + 5, M
= 1e9 + 7;
int dp
[N
][N
];
int main() {
ios
::sync_with_stdio(false);
cin
.tie(0);
cout
.tie(0);
int n
, r
;
cin
>> n
>> r
;
int a
= r
, b
= r
, x
, y
, w
;
for (int i
= 0; i
< n
; i
++) {
cin
>> x
>> y
>> w
;
x
++, y
++;
if (x
> a
) a
= x
;
if (y
> b
) b
= y
;
dp
[x
][y
] += w
;
}
for (int i
= 1; i
<= a
; i
++) {
for (int j
= 1; j
<= b
; j
++) {
dp
[i
][j
] = dp
[i
- 1][j
] + dp
[i
][j
- 1] - dp
[i
- 1][j
- 1] + dp
[i
][j
];
}
}
int ans
= 0;
for (int i
= r
; i
<= a
; i
++) {
for (int j
= r
; j
<= b
; j
++) {
ans
= max(ans
, dp
[i
][j
] - dp
[i
- r
][j
] - dp
[i
][j
- r
] + dp
[i
- r
][j
- r
]);
}
}
cout
<< ans
<< '\n';
return 0;
}
