激光炸弹 - 前缀和

痛定思痛。 2022-04-23 09:32 198阅读 0赞

一种新型的激光炸弹，可以摧毁一个边长为 R 的正方形内的所有的目标。

现在地图上有 N 个目标，用整数Xi,Yi表示目标在地图上的位置，每个目标都有一个价值Wi。

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

若目标位于爆破正方形的边上，该目标不会被摧毁。

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

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

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

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

**数据范围**  
0<N≤10000 ,  
0≤Xi,Yi≤5000  
**输入样例：**  
2 1  
0 0 1  
1 1 1  
**输出样例：**  
1

**时/空限制： 10s / 168MB**

**有关前缀和的相关知识：**

1.  一维前缀和  
    对于数列a\[1\], a\[2\], … , a\[n\]， 下标从1开始  
    前缀和s\[i\]表示 s\[i\] = a\[1\] + a\[2\] + … + a\[i\]  
    不难看出一维前缀和就是前 i 项的累加和，因此，我们很容易观察到 s\[i\] - s\[5\] ，就是从数列的第6项到第i项的累加和。所以我们可以在O(1)的时间内求出某个区间的累加和。
2.  二维前缀和  
    从一维前缀和很容易推广到二维  
    对于平面上的一些二维点（坐标都是正整数），前缀和s\[x\]\[y\]表示红色区域的所有点的累加和。![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjg1MDM2_size_16_color_FFFFFF_t_70]  
    我们现在知道了二维前缀和表示的就是原点与(x,y)点组成的与x轴，y轴平行的矩形内的点的和。那么我们怎么用二维的前缀和表示出图中红色的面积呢。  
    不难看出 红色面积 **S = s\[x1\]\[y1\] - s\[x2\]\[y1\] - s\[x1\]\[y2\] + s\[x2\]\[y2\]**  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjg1MDM2_size_16_color_FFFFFF_t_70 1]  
    所以利用二维前缀和可以在O(1)的时间内求出与x，y轴平行的矩形内所有点的权重的和。  
    到这里大家应该都知道二维前缀和的用法了，和我一样心里有个疑问，这么6的二维前缀和数组s\[i\]\[j\]是怎么构造出来的？ 这里其实是一个考点，采用动态规划的方式去构造，和刚才求红色部分的矩形类似，我们很容易得到**s\[i\]\[j\] = s\[i - 1\]\[j\] + s\[i\]\[j - 1\] - s\[i - 1\]\[j - 1\] + a\[i\]\[j\]**  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjg1MDM2_size_16_color_FFFFFF_t_70 2]

有了二维前缀和的相关知识，激光炸弹题目就迎刃而解了，我们只需要遍历一遍，求出长度为R的矩形内的总和，取最大值即可，需要注意的是边界线情况的处理，题目要求正方形边长上的不算数目，所以我们只需要把x，y坐标同时加一或者减一即可（让矩形错开一个位置）也就是只需要求边长是（R-1）的矩形即可，对应的代码上有注释。  
**激光炸弹代码**

#include <iostream>
    #include <algorithm>
    #include <cstring>
    
    using namespace std;
    
    const int N = 5005;
    
    int g[N][N];
    
    int main()
    {
        
        int n, r;
        
        
        memset(g, 0, sizeof(g));
        cin >> n >> r;
        int w = r, h = r;
        for(int i = 0, a, b, c;i < n;i++)
        {
        
            cin >> a >> b >> c;
            a++;b++;
            w = max(w, a);
            h = max(h, b);
            g[a][b] += c;
        }
        for(int i = 1;i <= w;i ++)
            for(int j = 1;j <= h;j++)
                g[i][j] += g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1];
        
        int res = 0;
        for(int i = r;i <= w;i++)
        {
        
            for(int j = r;j <= h;j++)
            {
        
            	// g[i][j] - g[i - r][j] - g[i][j - r] + g[i - r][j - r]
            	// 正常的应该是 g[i][j] - g[i - r - 1][j] - g[i][j - r - 1] + g[i - r - 1][j - r - 1]，
            	//这里我们把边界都加上1后，就能去除正方形边长上的炸弹数目
                res = max(res, g[i][j] - g[i - r][j] - g[i][j - r] + g[i - r][j - r]);
            }
        }
        
        cout << res << endl;
        
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjg1MDM2_size_16_color_FFFFFF_t_70]: /images/20220321/bcc92fe607f048008d28dfdc6bb9583b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjg1MDM2_size_16_color_FFFFFF_t_70 1]: /images/20220321/7dbc38b7b8c44ce9be400926893296e2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjg1MDM2_size_16_color_FFFFFF_t_70 2]: /images/20220321/b4e8f1e3034742bdbaad225876697862.png