Acwing 99 激光炸弹 （二维前缀和）
2020-12-28 18:26
标签：思想 就是 pre ios include long 思路 += 数据 地图上有 N 个目标，用整数Xi,Yi表示目标在地图上的位置，每个目标都有一个价值Wi。 注意：不同目标可能在同一位置。 现在有一种新型的激光炸弹，可以摧毁一个包含 R×R 个位置的正方形内的所有目标。 激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆炸范围，即那个正方形的边必须和x，y轴平行。 求一颗炸弹最多能炸掉地图上总价值为多少的目标。 输入格式 接下来N行，每行输入一组数据，每组数据包括三个整数Xi,Yi,Wi,分别代表目标的x坐标，y坐标和价值，数据用空格隔开。 输出格式 数据范围 前缀和我们都知道，对数组的每一个元素都进行一次累加操作，从而使我们可以在常数的复杂度求出区间的和，那么拓演到二维也会是一样，他所对应的差值，就是二维平面中矩阵的值之和。但是这个前缀和的求法会比一维稍微复杂一点，我们需要用到dp的思想，我们在求f[i][j]的时候可以假设f[i-1][j]和f[i][j-1]都已经求解得，那么我们可以画图看看，这里多加了一个以左上角为右下角的矩阵，那么我们把它减掉就好了。后面我们求解以r为边长的正方形的值的时候也是一样的思想。 Acwing 99 激光炸弹 （二维前缀和） 标签：思想 就是 pre ios include long 思路 += 数据 原文地址：https://www.cnblogs.com/hhlya/p/13307575.html题面
第一行输入正整数 N 和 R ,分别代表地图上的目标数目和正方形的边长，数据用空格隔开。
输出一个正整数，代表一颗炸弹最多能炸掉地图上目标的总价值数目。
0≤R≤109
0
0≤Wi≤1000
输入样例：
2 1
0 0 1
1 1 1
输出样例：
1思路
代码实现
#include
文章标题：Acwing 99 激光炸弹 （二维前缀和）
文章链接：http://soscw.com/index.php/essay/38881.html