<= 求赞qwq,码字不易,你的支持是我写作的动力
宣传一下算法提高课题解合集
99.激光炸弹
地图上有 $N$ 个目标,用整数 $X_{i}, Y_{i}$ 表示目标在地图上的位置,每个目标都有一个价值 $W_i$。
注意:不同目标可能在同一位置。
现在有一种新型的激光炸弹,可以摧毁一个包含 $R \times R$ 个位置的正方形内的所有目标。
激光炸弹的投放是通过卫星定位的,但其有一个缺点,就是其爆炸范围,即那个正方形的边必须和 $x,y$ 轴平行。
求一颗炸弹最多能炸掉地图上总价值为多少的目标。
输入格式
第一行输入正整数 $N$ 和 $R$,分别代表地图上的目标数目和正方形的边长,数据用空格隔开。
接下来 $N$ 行,每行输入一组数据,每组数据包括三个整数 $X_{i}, Y_{i}, W_{i}$,分别代表目标的 $x$ 坐标,$y$ 坐标和价值,数据用空格隔开。
输出格式
输出一个正整数,代表一颗炸弹最多能炸掉地图上目标的总价值数目。
数据范围
$0 \le R \le 10^9$
$0 < N \le 10000$,
$0 \le X_{i}, Y_{i} \le 5000$
$0 \le W_i \le 1000$
输入样例:
2 1
0 0 1
1 1 1
输出样例:
1
二维前缀和模板题:
注意 r 的范围和平面区间的计算
$mp[][]$ 数组:二维前缀和,用来 $O(1)$ 时间计算平面数字和
$mp[i][j] - mp[i - r][j] - mp[i][j - r] + mp[i - r][j - r]$
$ans$:最终总价值数目
$n$:目标个数,$r$:正方形的边长
c++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 5009;
int mp[N][N];//二位前缀和数组
int n, r, ans = 0;
int main()
{
cin >> n >> r;
r = min(r, 5001);
for(int i = 1, x, y, w;i <= n;++ i)
{
cin >> x >> y >> w;
mp[x + 1][y + 1] += w;//此时 mp 数组的含义就是初始地图
}
for(int i = 1;i <= 5001;++ i)//坐标最多 5000
for(int j = 1;j <= 5001;++ j)//按顺序枚举坐标
mp[i][j] = mp[i - 1][j] + mp[i][j - 1] - mp[i - 1][j - 1] + mp[i][j];
//注意顺序
for(int i = r;i <= 5001;++ i)
for(int j = r;j <= 5001;++ j)//状态计算
ans = max(ans, mp[i][j] - mp[i - r][j] - mp[i][j - r] + mp[i - r][j - r]);
cout << ans << endl;
return 0;
}
为什么调试不对,能通过?
感谢分享
大佬问什么是mp[x + 1][y + 1]+=w,而不是mp[x ][y ]
题目给的坐标是从0开始的。把所有点的横坐标与纵坐标加1是为了防止计算前缀和时数组越界
子矩阵的和不是s[x2, y2] - s[x1 - 1, y2] - s[x2, y1 - 1] + s[x1 - 1, y1 - 1]吗,为什么这里不用减。打扰了Hhhhh
因为炸弹炸不到边界
推出来是 i+1-r-1