激光炸弹

思路
首先题目让我们求最多能炸掉多少的目标，我们可以用F[i][j]来代表(Xi,Yi)的值，而且题目让我们求以r为边长的正方形覆盖的最大权值，很明显可以想到二维的前缀和

为什么用二维前缀和 ：
就是预处理的思想，在O（1）的时间内求出二维数组中的某个矩阵的区域内的数字之和

公式
F[i][j] = F[i][j-1]+F[i-1][j]+a[i][j]-F[i-1][j-1],不过可以通过求自身的前缀和来稍稍优化下内存= =；

附蒟蒻的代码

#include <bits/stdc++.h>

using namespace std;
const int N = 5010;

int g[N][N];
int n,r;
int main ()
{
    int x,y,v;
    scanf("%d%d",&n,&r);

    int a = r,b = r;
    for (int i = 1 ; i <= n ; i++)
    {
        cin>>x>>y>>v;
        x++,y++;
        a = max(a,x),b = max(b,y);
        g[x][y]+=v;
    }

    for (int i = 1 ; i <= a ; i++)
    {
        for (int j = 1 ; j <= b ; 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 <= a ; i++)
    {
        for (int j = r ; j <= b ; j++)
        res = max(res,g[i][j]-g[i-r][j]-g[i][j-r]+g[i-r][j-r]);
    }

    cout<<res<<endl;
    return 0;
}