题目链接

算法竞赛进阶指南-12.激光炸弹

cin >> n >> r;

题目意思就是有n个目标，炸弹范围是r * r

接下来输入n行目标的坐标x, y 和其价值w，

要求输出一个炸弹范围最多能包含多少总价值的目标。

Method : 前缀和

显然是二维的前缀和问题。

这道题比较难的点:

1. 坐标的偏移处理, s[++ x][++ y] += w
2. 内存限制很严格, 必须在原数组上做前缀和覆盖，不能另外申请数组
3. 数据点严格, 不加这两句过不了最后两个点，r = min(r, N - 1); x_max = y_max = r;

#include <iostream>

using namespace std;

const int N = 5e3 + 7;

int n, r;
int x_max, y_max;
//  int w[N][N];
int s[N][N];

int main() {
    cin >> n >> r;

    r = min(r, N - 1);
    x_max = y_max = r;

    for (int i = 1; i <= n; i ++) {
        int x, y, curw;
        scanf("%d %d %d", &x, &y, &curw);
        s[++ x][++ y] += curw;

        x_max = max(x_max, x);
        y_max = max(y_max, y);
    }

    // 预处理前缀和
    for (int i = 1; i <= x_max; i ++) {
        for (int j = 1; j <= y_max; j ++) {
            s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + s[i][j];
        }
    }

    int res = 0;
    // 以右下坐标为原点统计
    // 右下点(x2, y2) : (i, j)   左上点(x1, y1) : (i - r + 1, j - r + 1)
    for (int i = r; i <= x_max; i ++) {
        for (int j = r; j <= y_max; j ++) {
            int tar = s[i][j] - s[i][j - r] - s[i - r][j] + s[i - r][j - r];
            res = max(res, tar);
        }
    }

    // 以左上坐标为原点统计
    // for (int i = 1; i <= x_max - r + 1; i ++) {
    //     for (int j = 1; j <= y_max - r + 1; j ++) {
    //         int tar = s[i + r - 1][j + r - 1] - s[i + r - 1][j - 1] - s[i - 1][j + r - 1] + s[i - 1][j - 1];
    //         res = max(res, tar);
    //     }
    // }

    cout << res << endl;

    return 0;
}

复杂度分析

• 时间复杂度${O(x_{max} * y_{max})}$ 。

• 空间复杂度${O(N * N)}$。