AcWing:99. 激光炸弹(前缀和)
2024-09-05 06:03:10
一种新型的激光炸弹,可以摧毁一个边长为 RR 的正方形内的所有的目标。
现在地图上有 NN 个目标,用整数Xi,YiXi,Yi表示目标在地图上的位置,每个目标都有一个价值WiWi。
激光炸弹的投放是通过卫星定位的,但其有一个缺点,就是其爆炸范围,即那个边长为 RR 的正方形的边必须和x,yx,y轴平行。
若目标位于爆破正方形的边上,该目标不会被摧毁。
求一颗炸弹最多能炸掉地图上总价值为多少的目标。
输入格式
第一行输入正整数 NN 和 RR ,分别代表地图上的目标数目和正方形的边长,数据用空格隔开。
接下来NN行,每行输入一组数据,每组数据包括三个整数Xi,Yi,WiXi,Yi,Wi,分别代表目标的xx坐标,yy坐标和价值,数据用空格隔开。
输出格式
输出一个正整数,代表一颗炸弹最多能炸掉地图上目标的总价值数目。
数据范围
0<N≤100000<N≤10000,
0≤Xi,Yi≤50000≤Xi,Yi≤5000
输入样例:
2 1
0 0 1
1 1 1
输出样例:
1
算法:前缀和
题解:利用前缀和来求解,算出每个位置的前缀和值来,利用前缀和的减法操作,来求得你需要取得区间,然后遍历得到最大值。
#include <iostream>
#include <cstdio> using namespace std; const int maxn = 5e3+; int arr[maxn][maxn];
int b[maxn]; int main() {
int n, m;
scanf("%d %d", &n, &m);
int row = m, col = m;
for(int i = ; i <= n; i++) {
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
u++;
v++;
arr[u][v] = w;
row = max(row, u);
col = max(col, v);
}
for(int i = ; i <= row; i++) {
for(int j = ; j <= col; j++) {
b[j] = b[j - ] + arr[i][j]; //此行的前缀和数组
arr[i][j] = arr[i - ][j] + b[j]; //上一行当前位置的前缀和加上此行当前位置的前缀和
}
}
int ans = ;
for(int i = m; i <= row; i++) {
for(int j = m; j <= col; j++) {
ans = max(ans, arr[i][j] - arr[i - m][j] - arr[i][j - m] + arr[i - m][j - m]); //当前位置的前缀和减去前面多余的部分
}
}
cout << ans << endl;
return ;
}
最新文章
- mysqlbinlog
- headroom.js –在不需要页头时将其隐藏
- jquery的$().each,$.each的区别
- oracle 查询结果集运算
- 查看mysql,apache,php,nginx编译参数
- jdk
- ACM之Java速成(2)
- 推荐资料——最受网友力荐的30份HTML前端开发资料
- 盘点 OSX 上最佳的 DevOps 工具
- CSS3 旋转的八卦图
- 用Javascript的for循环输出质数
- haskell,lisp,erlang你们更喜欢哪个?
- Embedding Lua, in Scala, using Java(转)
- Go语言Web框架gwk介绍 3
- mysql加密解密方式用法
- [.NET] 《Effective C#》快速笔记 - C# 中的动态编程
- python面向对象--类
- sqldeveloper 重置java.exe路径方法
- VUE中过了一遍还不熟悉的东西
- python概念-常用模块之究竟你是什么鬼