首页 > 代码库 > BZOJ1218 [HNOI2003]激光炸弹

BZOJ1218 [HNOI2003]激光炸弹

题目后面写着DP就当它是DP吧。。

本来是扫描线+线段树的说,但是捏5000^2还是能过滴,于是暴力枚举正方形+所谓的DP就解决了。

 1 #include <cstdio> 2 #include <cmath> 3 #include <algorithm> 4  5 using namespace std; 6  7 int a[5005][5005]; 8  9 int main(){10     int n, R, x, y, c, i, j, ans = 0, maxc = 5002;11     scanf("%d%d", &n ,&R);12     while (n--){13         scanf("%d%d%d", &x, &y, &c);14         a[x + 1][y + 1] = c;15     }16     for (int i = 1; i < maxc; ++i)17         for (int j = 1; j < maxc; ++j)18             a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];19     maxc -= R;20     for (int i = 0; i < maxc; ++i)21         for (int j = 0; j < maxc; ++j)22             ans = max(ans, a[i + R][j + R] + a[i][j] - a[i + R][j] - a[i][j + R]);23     printf("%d\n", ans);        24     return 0;    25 }
View Code

 

BZOJ1218 [HNOI2003]激光炸弹