题目描述一种新型的激光炸弹，可以摧毁一个边长为R的正方形内的所有的目标。现在地图上有n(N ≤ 10000)个目标，用整数Xi,Yi(其值在[0,5000])表示目标在地图上的位置，每个目标都有一个价值。激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆破范围，即那个边长为R的正方形的边必须和
展开全文
题意：一种新型的激光炸弹，可以摧毁一个边长为R的正方形内的所有的目标。现在地图上有n(N ≤ 10000)个目标，用整数Xi,Yi(其值在[0,5000])表示目标在地图上的位置，每个目标都有一个价值。激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆破范围，即那个边长为R的正方形的边必须和x
展开全文
题意 一种新型的激光炸弹，可以摧毁一个边长为R的正方形内的所有的目标。 现在地图上有n(N ≤ 10000)个目标，用整数Xi,Yi(其值在[0,5000])表示目标在地图上的位置，每个目标都有一个价值。激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆破范围，即那个边长为R的正方形的边必须和
展开全文
5001*5001，量太大了，直接用前缀和 整一个5001*5001的二维数组来对应整个地图，数组中的元素表示当前坐标上目标的价值（无目标即为0） 先很普通的用循环记录每个目标的坐标和价值，然后再循环计算前缀和。计算时，每个点[i][j]上记录的价值和为 [ i ][ j ]+[ i-1 ][ j
展开全文
链接：https://ac.nowcoder.com/acm/problem/20032
来源：牛客网
题目描述
一种新型的激光炸弹，可以摧毁一个边长为R的正方形内的所有的目标。
现在地图上有n(N ≤ 10000)个目标，用整数Xi,Yi(其值在[0
展开全文
激光炸弹（二维前缀和） -（图画的有点丑意思意思就行了）学习二维前缀和首先要了解的是二维前缀和是哪些的和---（在下图中A点的前缀和是红色部分，B点的前缀和是红色加绿色部分（至于是哪一部分绿色自己想想也知道），C点的同B点，D点的是红色加所有绿色部分再加白色部分,这里可以这样理解sum[i][j]的
展开全文
//炸弹的边长为r，能够包括的点数最多为人r^2个点，那么我们对点数为r^2的子矩阵求和，找出其中最大值；#include<iostream>using namespace std;int map[5001][5001];int ans[5001][5001];int main(){
展开全文
思路首先题目让我们求最多能炸掉多少的目标，我们可以用F[i][j]来代表(Xi,Yi)的值，而且题目让我们求以r为边长的正方形覆盖的最大权值，很明显可以想到二维的前缀和 为什么用二维前缀和 ：就是预处理的思想，在O（1）的时间内求出二维数组中的某个矩阵的区域内的数字之和 公式 F[i][j] = F
展开全文
//激光炸弹
//本质最大子矩阵，再本质最大连续区间，自然用前缀和做
#include <bits/stdc++.h>
using namespace std;
int arr[5050][5050];//输入矩阵
int ans[5050][5050];//结果矩阵，保存矩阵的
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
