[HNOI2003]激光炸弹(二维前缀和)
[HNOI2003]激光炸弹
https://ac.nowcoder.com/acm/problem/20032
题目描述
一种新型的激光炸弹，可以摧毁一个边长为R的正方形内的所有的目标。
现在地图上有n(N ≤ 10000)个目标，用整数Xi,Yi(其值在[0,5000])表示目标在地图上的位置，每个目标都有一个价值。
激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆破范围，即那个边长为R的正方形的边必须和x，y轴平行。
若目标位于爆破正方形的边上，该目标将不会被摧毁。
输入描述:
输入文件的第一行为正整数n和正整数R，接下来的n行每行有3个正整数，分别表示 xi，yi ，vi 。
输出描述:
输出文件仅有一个正整数，表示一颗炸弹最多能炸掉地图上总价值为多少的目标（结果不会超过32767）。
示例1
输入
2 1 0 0 1 1 1 1
输出
1
思路
二维前缀和，找(r-1) * (r-1)区域的最大值，暴力搜索即可
代码
//[HNOI2003]激光炸弹(二维前缀和)
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 5010;
int n , r;
int x , y , v;
int s[N][N];
int main()
{
scanf("%d %d" , &n , &r);
while(n--)
{
scanf("%d %d %d" , &x , &y , &v);
s[x + 1][y + 1] = max(s[x + 1][y + 1] , v);
}
for(int i = 1 ; i < N ; i++)
{
for(int j = 1 ; j < N ; j++)
s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
}
int ans = 0;
for(int i = r ; i < N ; i++)
{
for(int j = r ; j < N ; j++)
ans = max(ans , s[i][j] - s[i - r][j]
- s[i][j - r] + s[i - r][j - r]);
}
printf("%d\n" , ans);
return 0;
}
牛客算法竞赛入门课第一节习题题解 文章被收录于专栏
入门课第一节习题题解
恒生电子公司氛围 51人发布
