首页 > 代码库 > 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 }
BZOJ1218 [HNOI2003]激光炸弹
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。