signed

QiShunwang

“诚信为本、客户至上”

激光炸弹(经典矩阵前缀和)

2021/4/26 21:05:29   来源:

【题目描述】
地图上有 N 个目标,用整数 Xi,Yi 表示目标在地图上的位置,每个目标都有一个价值 Wi。

注意:不同目标可能在同一位置。

现在有一种新型的激光炸弹,可以摧毁一个包含 R×R 个位置的正方形内的所有目标。

激光炸弹的投放是通过卫星定位的,但其有一个缺点,就是其爆炸范围,即那个正方形的边必须和 x,y 轴平行。

求一颗炸弹最多能炸掉地图上总价值为多少的目标。

【输入格式】
第一行输入正整数 N 和 R,分别代表地图上的目标数目和正方形的边长,数据用空格隔开。

接下来 N 行,每行输入一组数据,每组数据包括三个整数 Xi,Yi,Wi,分别代表目标的 x 坐标,y 坐标和价值,数据用空格隔开。

【输出格式】
输出一个正整数,代表一颗炸弹最多能炸掉地图上目标的总价值数目。

在这里插入图片描述

【解题思路】

注意题目给的提醒:不同的目标可能会出现在同一位置,因此我们要用+=来储存这个坐标的物品价值,并且要取长和宽的最大值确保不会过界,然后依次枚举所有位置坐标,不用担心加了多余的,因为在全局变量中开的数组默认元素全为0,然后计算前缀和运算最后相减即可

【代码描述】

#include <iostream>

using namespace std;

int n,r;
const int N = 5002;
int s[N][N]; //全局变量赋值为0
int main()
{
    scanf("%d%d",&n,&r);
    int p = r, q = r;
    while(n--)
    {
        int x,y,v;
        scanf("%d%d%d",&x,&y,&v);
        x++;
        y++;
        s[x][y] += v; //可能会在同一个位置,所以是+=
        p = max(p,x);
        q = max(q,y);
    }
    
    for(int i = 1;i <= p;i++)
    for(int j = 1;j <= q;j++)
    s[i][j] = s[i][j-1] + s[i-1][j] - s[i-1][j-1] + s[i][j]; //此处后面的s[i][j]意为a[i][j]
    
    int res = 0;
    
    for(int i = r;i <= p;i++)
    for(int j = r;j <= q;j++)
    {
         res = max(res,s[i][j] - s[i-r][j] - s[i][j-r] + s[i-r][j-r]);
    }
    
    printf("%d",res);
}