Acwing-99-激光炸弹(二维前缀和)
2024-10-07 00:46:35
链接:
https://www.acwing.com/problem/content/101/
题意:
一种新型的激光炸弹,可以摧毁一个边长为 R 的正方形内的所有的目标。
现在地图上有 N 个目标,用整数Xi,Yi表示目标在地图上的位置,每个目标都有一个价值Wi。
激光炸弹的投放是通过卫星定位的,但其有一个缺点,就是其爆炸范围,即那个边长为 R 的正方形的边必须和x,y轴平行。
若目标位于爆破正方形的边上,该目标不会被摧毁。
求一颗炸弹最多能炸掉地图上总价值为多少的目标。
思路:
二维前缀和搞一下,然后暴力即可.
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 5e3+10;
int Sum[MAXN][MAXN];
int n, r;
int main()
{
scanf("%d%d", &n, &r);
int x, y, v;
int maxx = r, maxy = r;
for (int i = 1;i <= n;i++)
{
scanf("%d%d%d", &x, &y, &v);
x++, y++;
Sum[x][y] = v;
maxx = max(maxx, x);
maxy = max(maxy, y);
}
for (int i = 1;i <= maxx;i++)
{
for (int j = 1;j <= maxy;j++)
Sum[i][j] = Sum[i-1][j]+Sum[i][j-1]-Sum[i-1][j-1]+Sum[i][j];
}
int res = 0;
for (int i = r;i <= maxx;i++)
{
for (int j = r;j <= maxy;j++)
{
res = max(res, Sum[i][j]-Sum[i][j-r]-Sum[i-r][j]+Sum[i-r][j-r]);
}
}
printf("%lld\n", res);
return 0;
}
最新文章
- WCF学习之旅—WCF服务的WAS寄宿(十二)
- 两种设置disabled属性以及三种方法移除disabled属性
- javascript学习笔记1-document.write
- 详细解读Jquery各Ajax函数:$.get(),$.post(),$.ajax(),$.getJSON()
- nandflash操作详解
- 快递查询API接口(trackingmore)
- 现代程序设计——homework-09
- VS2013开发Windows服务项目
- explain简介
- 【译】在Asp.Net中操作PDF – iTextSharp - 使用表格
- BackgroundWorker组件使用总结
- oracle 小测
- lgp20151222 java中如何将Object类型转换为int类型
- java8 Stream操作
- c++趣味之返回void
- c语言学习5
- MT【19】舒尔不等式设计理念及证明
- python接口自动化测试六:时间戳,防重复处理
- pymysql-connect阻塞
- 解决js中window.location.href不工作的问题
热门文章
- eclipse 导入项目出现的问题汇总
- 使用PowerShell 自动创建DFS复制组
- 使用PowerShell 在域内远程安装DFS
- 10分钟学会web通讯的四种方式,短轮询、长轮询(comet)、长连接(SSE)、WebSocket
- 转-性能优化中CPU、内存、磁盘IO、网络性能的依赖
- Java基础(七)
- 创建Maven Web项目时很慢解决办法
- 使用idea关联mysql时报错Server returns invalid timezone. Go to &#39;Advanced&#39; tab and set &#39;serverTimezon&#39;
- Makefile 书写规则
- %300为0的个数(牛客第四场)--	number