题目
题目描述:一种新型的激光炸弹,可以摧毁一个边长为R的正方形内的所有的目标。
现在地图上有n(N ≤ 10000)个目标,用整数Xi,Yi(其值在[0,5000])表示目标在地图上的位置,每个目标都有一个价值。
激光炸弹的投放是通过卫星定位的,但其有一个缺点,就是其爆破范围,即那个边长为R的正方形的边必须和x,y轴平行。
若目标位于爆破正方形的边上,该目标将不会被摧毁。
输入文件的第一行为正整数n和正整数R,接下来的n行每行有3个正整数,分别表示 xi,yi ,vi 。
输出文件仅有一个正整数,表示一颗炸弹最多能炸掉地图上总价值为多少的目标(结果不会超过32767)。
解析
这道题看到的时候,我虎躯一震,写过差不多的!就可以直接二维前缀和。
- 我不会乱说是因为我到现在还不会线段树的orzzzz
先看题吧:
- 题目告诉我们:我们已知了爆破的正方形边长,要求可以爆破的最大值。
首先是我们的暴力灵感:
- 我们将左上角点代表方阵,然后计算方阵里面的值,遍历一圈然后选最大值就好,不过超时是肯定的。
巨巨曾经说过:我们写代码要从会暴力开始提升境界,然后我们来想一下怎么优美的暴力:
- 我们上面讲到了,我们可以用一个顶点代替一个方阵。但是我们上面是用了遍历这个方阵,我们何不真用这个点代替方阵呢!
- 什么叫真的代替方阵!就是前缀和呀!!!我们这个二维前缀和储存:以原点和该点为对角线的矩形内的数字之和。
- 也就是说,我们在判断某一个点时,就能知道他所代表的矩形的值(计算怎么办,下面会讲)。
- 这就是这里二维前缀和的基本思路了。
那么这个前缀和怎么构造呢?
- 其实很简单,知道递推式我们很简单就能得到了:
sum[i][j] = mp[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1]; //某一点的前缀和 = 该点值 + 上面一点的前缀和 + 左边一点的前缀和 - 上边和左边重叠的部分
那这个前缀和该怎么运算呢?怎么弄成方阵呢?
- 我们还是和上面一样,先看图:
- 从图里面我们还是发现,得到某一个方阵的方法是去掉左边和上面的区间,在加上重合的区间。
不过要注意这里是k*k,所以减去的应该是 i - k 和 j - k 的位置的矩形。 - 所以我们判断的公式应该是:
sum[x][y] - sum[x - k][y] - sum[x][y - k] + sum[x - k][y - k]
打代码咯:
- 所以我们先讲原来的矩阵保存下来。
- 然后初始化前缀和(详情看上方小专栏)。
- 随后我们就可以判断方阵递推啦。
- 详情看代码趴~
AC代码
#include <iostream> #include <algorithm> using namespace std; #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); //代码预处理区 const int MAX = 5e3 + 7; int sum[MAX][MAX]; //全局变量区 int calc(int i, int j, int r) { return sum[i][j] - sum[i - r][j] - sum[i][j - r] + sum[i - r][j - r]; } //函数预定义区 int main() { IOS; int n, r; cin >> n >> r; for (int i = 1; i <= n; i++) { int x, y, val; cin >> x >> y >> val; sum[x + 1][y + 1] = val; } for (int i = 1; i <= 5e3; i++) for (int j = 1; j <= 5e3; j++) sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1]; int ans = 0; for (int i = r; i <= 5e3; i++) for (int j = r; j <= 5e3; j++) ans = max(ans, calc(i, j, r)); cout << ans << endl; return 0; } //函数区