题目描述

地图上有 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 即为所求,这样,我们就得到了一颗炸弹最多能炸掉地图上总价值为多少的目标。

代码实现

#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;
}
分类: PrefixSum

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status