西安烽盈网站建设,铜陵网站建设维护,医院网站优化,wordpress 云落主题题目
地图上有 N 个目标#xff0c;用整数 Xi,Yi 表示目标在地图上的位置#xff0c;每个目标都有一个价值 Wi。
注意#xff1a;不同目标可能在同一位置。
现在有一种新型的激光炸弹#xff0c;可以摧毁一个包含 RR 个位置的正方形内的所有目标。
激光炸弹的投放是通过…题目
地图上有 N 个目标用整数 Xi,Yi 表示目标在地图上的位置每个目标都有一个价值 Wi。
注意不同目标可能在同一位置。
现在有一种新型的激光炸弹可以摧毁一个包含 R×R 个位置的正方形内的所有目标。
激光炸弹的投放是通过卫星定位的但其有一个缺点就是其爆炸范围即那个正方形的边必须和 xy 轴平行。
求一颗炸弹最多能炸掉地图上总价值为多少的目标。
输入格式
第一行输入正整数 N 和 R分别代表地图上的目标数目和正方形包含的横纵位置数量数据用空格隔开。
接下来 N 行每行输入一组数据每组数据包括三个整数 Xi,Yi,Wi分别代表目标的 x 坐标y 坐标和价值数据用空格隔开。
输出格式
输出一个正整数代表一颗炸弹最多能炸掉地图上目标的总价值数目。
数据范围
0 ≤ R ≤ 1e9 0 N ≤ 10000 0 ≤ Xi , Yi ≤ 5000 0 ≤ Wi ≤ 1000
输入样例
2 1
0 0 1
1 1 1输出样例
1
思路 本题用到了前缀和的思想我们可以先将目标储存到地图中然后计算点00到点xiyi为矩形的面积中的目标价值总和记录到g[xi][yi]中公式如下
g[i][j] g[i][j] g[i - 1][j] g[i][j - 1] - g[i - 1][j - 1]; 使用g[ ][ ]数组的时候只需求出面积为r - 1*r - 1的正方形中目标价值总和公式如下
g[i][j] g[i][j] - g[i - 1][j] - g[i][j - 1] g[i - 1][j - 1];
代码
#includebits/stdc.h
using namespace std;
const int N 5010;
int n,r,ans;
int g[N][N];int main()
{cin n r;// 将n个目标输入地图之中while(n --){int a,b,c;cin a b c;g[ a][ b] c;}// 求二维数组的前缀和for(int i 1; i N; i ){for(int j 1; j N; j ){g[i][j] g[i][j] g[i - 1][j] g[i][j - 1] - g[i - 1][j - 1];}}// 暴力求解找出所有区域价值的最大值for(int i 1; i N; i ){for(int j 1; j N; j ){int a i - r; if(a 0) a 0;int b j - r; if(b 0) b 0;int sum g[i][j] - g[a][j] - g[i][b] g[a][b];ans max(ans,sum);}}cout ans endl;return 0;
}
题目来自99. 激光炸弹 - AcWing题库
