题目后面写着DP就当它是DP吧。。
本来是扫描线+线段树的说，但是捏5000^2还是能过滴，于是暴力枚举正方形+所谓的DP就解决了。
1 /************************************************************** 2 Problem: 1218 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:2860 ms 7 Memory:98656 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 #include <cmath> 12 #include <algorithm> 13 14 using namespace std; 15 16 int a[5005][5005]; 17 18 int main(){ 19 int n, R, x, y, c, i, j, ans = 0, maxc = 5002; 20 scanf("%d%d", &n ,&R); 21 while (n--){ 22 scanf("%d%d%d", &x, &y, &c); 23 a[x + 1][y + 1] = c; 24 } 25 for (int i = 1; i < maxc; ++i) 26 for (int j = 1; j < maxc; ++j) 27 a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1]; 28 maxc -= R; 29 for (int i = 0; i < maxc; ++i) 30 for (int j = 0; j < maxc; ++j) 31 ans = max(ans, a[i + R][j + R] + a[i][j] - a[i + R][j] - a[i][j + R]); 32 printf("%d ", ans); 33 return 0; 34 }