激光炸弹

题意：

地图上有 N 个目标，用整数$X_i,Y_i$表示目标在地图上的位置，每个目标都有一个价值$W_i$

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

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

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

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

分析：

1.先求出前缀和数组
2.把全部边长是R-1(边长上的不算)的数组遍历一遍，然后取最大值（最多只有$n^2$)

复杂度：O($n^2$)

输入&预处理：

    cin>>N>>R;
    int n=R,m=R;//长和宽
    for(int i=0,x,y,w;i<N;i++)
    {
        cin>>x>>y>>w;
        x++;
        y++;
        //为了方便处理边界，把前缀和定义从1开始，所以开头要++
        n=max(n,x);
        m=max(m,y);
        //判断长和宽的边界
        g[x][y]+=w;//将他们的价值放进数组里
    }

求二维前缀和:

for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            g[i][j]+=g[i-1][j] + g[i][j-1] -g[i-1][j-1];
            //g[i-1][j]=sum1,g[i][j-1]=sum2,g[i-1][j-1]=sum3
        }
    }

求最大值:

int ans=0;
    for(int i=R;i<=n;i++)//长
    {
        for(int j=R;j<=m;j++)//宽
        {
            ans=max(ans,g[i][j] - g[i-R][j] - g[i][j-R] +g[i-R][j-R]);
        }
    }

Ac Code:

#include <iostream>
#include <algorithm>
using namespace std;

const int S=5010;
int g[S][S];//价值
int N,R;

int main()
{
    cin>>N>>R;
    int n=R,m=R;//长和宽
    for(int i=0,x,y,w;i<N;i++)
    {
        cin>>x>>y>>w;
        x++;
        y++;
        //为了方便处理边界，把前缀和定义从1开始，所以开头要++
        n=max(n,x);
        m=max(m,y);
        //判断长和宽的边界
        g[x][y]+=w;//将他们的价值放进数组里
    }
    //输入&预处理

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            g[i][j]+=g[i-1][j] + g[i][j-1] -g[i-1][j-1];
            //g[i-1][j]=sum1,g[i][j-1]=sum2,g[i-1][j-1]=sum3
        }
    }
    //求二维前缀和

    int ans=0;
    for(int i=R;i<=n;i++)//长
    {
        for(int j=R;j<=m;j++)//宽
        {
            ans=max(ans,g[i][j] - g[i-R][j] - g[i][j-R] +g[i-R][j-R]);
        }
    }
    //求最大值

    cout<<ans<<endl;

    return 0;
}