目录
1.题目2.代码
1.题目
地图上有 N 个目标，用整数Xi,Yi表示目标在地图上的位置，每个目标都有一个价值Wi。
注意：不同目标可能在同一位置。
现在有一种新型的激光炸弹，可以摧毁一个包含 R×R 个位置的正方形内的所有目标。
激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆炸范围，即那个正方形的边必须和x，y轴平行。
求一颗炸弹最多能炸掉地图上总价值为多少的目标。
输入格式 第一行输入正整数 N 和 R ,分别代表地图上的目标数目和正方形的边长，数据用空格隔开。
接下来N行，每行输入一组数据，每组数据包括三个整数Xi,Yi,Wi,分别代表目标的x坐标，y坐标和价值，数据用空格隔开。
输出格式 输出一个正整数，代表一颗炸弹最多能炸掉地图上目标的总价值数目。
数据范围 0≤R≤109 0<N≤10000, 0≤Xi,Yi≤5000 0≤Wi≤1000 输入样例： 2 1 0 0 1 1 1 1 输出样例： 1
2.代码
#include<iostream>
#include<cstdio>
#include<algorithm>
const int maxn
= 5e3 + 10;
using namespace std
;
int f
[maxn
][maxn
];
int main()
{
int N
, R
,n
,m
;
cin
>> N
>> R
;
n
= R
, m
= R
;
for (int i
= 1; i
<= N
; i
++)
{
int x
, y
, w
;
cin
>> x
>> y
>> w
;
x
++,y
++;
n
= max(n
, x
);
m
= max(m
, y
);
f
[x
][y
] += w
;
}
int ans
= 0;
for (int i
= 1; i
<= n
; i
++)
{
for (int j
= 1; j
<= m
; j
++)
{
f
[i
][j
] += f
[i
][j
- 1] + f
[i
- 1][j
] - f
[i
- 1][j
- 1];
}
}
for (int i
= R
; i
<= n
; i
++)
{
for (int j
= R
; j
<= m
; j
++)
{
ans
= max(ans
, f
[i
][j
] - f
[i
][j
- R
] - f
[i
- R
][j
] + f
[i
- R
][j
- R
]);
}
}
cout
<< ans
<< endl
;
return 0;
}
