Loading... [来自KeChang](https://blog.silvery.me/) ### 题目描述 地图上有 N 个目标，用整数 Xi, Yi 表示目标在地图上的位置，每个目标都有一个价值 Wi。 注意：不同目标可能在同一位置。 现在有一种新型的激光炸弹，可以摧毁一个包含 R×R 个位置的正方形内的所有目标。 激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆炸范围，即那个正方形的边必须和 x，y 轴平行。 求一颗炸弹最多能炸掉地图上总价值为多少的目标。 ### 输入格式 第一行输入正整数 N 和 R，分别代表地图上的目标数目和正方形包含的横纵位置数量，数据用空格隔开。 接下来 N 行，每行输入一组数据，每组数据包括三个整数 Xi, Yi, Wi，分别代表目标的 x 坐标，y 坐标和价值，数据用空格隔开。 ### 输出格式 输出一个正整数，代表一颗炸弹最多能炸掉地图上目标的总价值数目。 ### 数据范围 0 ≤ R ≤ 10^9 0 < N ≤ 10000, 0 ≤ Xi, Yi ≤ 5000 0 ≤ Wi ≤ 1000 ### 输入样例： ``` 2 1 0 0 1 1 1 1 ``` ### 输出样例： ``` 1 ``` ### 题目分析 这道题目可以使用前缀和的思想来解决。我们首先创建一个二维数组 g[N][N] 来表示每个位置的累积价值，其中 N = 5e3 + 10。 接着，我们读入地图上的 N 个目标的信息，并将它们的价值累加到相应的位置上（这里加 1 是因为题目给出的坐标范围是从 0 到 5000，而数组是从 1 到 5001）。 然后，我们对二维数组 g 进行前缀和的预处理，使得 g[i][j] 表示以 (i, j) 为右下角的矩形区域内的目标价值之和。 接下来，我们通过两重循环遍历所有可能的正方形爆炸区域，即以 (i, j) 为右下角，边长为 R 的正方形。我们使用 x1、y1、x2、y2 表示该正方形的左上角坐标和右下角坐标。 对于每个正方形，我们可以利用前缀和数组快速计算该区域内目标的总价值。具体地，我们可以通过以下公式得到该正方形区域内目标价值的总和： `g[x2][y2] - g[x2][y1 - 1] - g[x1 - 1][y2] + g[x1 - 1][y1 - 1]` 最后，我们在遍历过程中维护一个最大值 ans，它代表炸弹最多能炸掉地图上目标的总价值数目。 最后输出 ans 即为所求，这样，我们就得到了一颗炸弹最多能炸掉地图上总价值为多少的目标。 ### 代码实现 ```cpp #include <iostream> using namespace std; const int N = 5e3 + 10; int g[N][N], n, x, y, w, r, ans; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> r; while (n--) { cin >> x >> y >> w; g[x + 1][y + 1] += w; // 将目标的价值累加到相应位置 } for (int i = 1; i < N; ++i) for (int j = 1; j < N; ++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 x1 = (i - r + 1 >= 1 ? i - r + 1 : 1), // 正方形左上角横坐标 y1 = (j - r + 1 >= 1 ? j - r + 1 : 1), // 正方形左上角纵坐标 x2 = i, y2 = j; // 正方形右下角坐标 ans = max(ans, g[x2][y2] - g[x2][y1 - 1] - g[x1 - 1][y2] + g[x1 - 1][y1 - 1]); // 计算该正方形区域内的目标总价值，并更新答案 } } cout << ans; // 输出最大价值 return 0; } ``` 最后修改：2023 年 08 月 06 日 © 允许规范转载 赞 1 如果觉得我的文章对你有用，请随意赞赏