99.激光炸弹

原题链接：Acwing99. 激光炸弹

解题思路

因为X_i,Y_i的值在0~5000之间，所以我们可以建立一个二维数组 A,其中 A[i,j] 就等于位置 (i,j) 上的所有目标的价值之和。即对于每个目标，令 A[X_i,Y_i]+=W_i。
接下来我们求出 A 的二维前缀和 S,即：

S[i,j] = ∑(i,x=1)∑(j,y=1)A[z,y]

如下图所示,我们再观察 S[i,j],S[i-1,j],S[i,j-1],S[i-1,j-1] 的关系。

容易得到如下递推式：

S[i,j] = S[i-1,j] + S[i,j-1] - S[i-1,j-1] + A[i,j]

同理，对于任意一个边长为 R 的正方形，我们有：

∑(i,x=i-R+1)∑(j,y=j-R+1) A[x,y] = S[i,j] - S[i-R,j] - S[i,j-R] + S[i-R,j-R]

因此我们只需要 O(N²) 递推求出二维前缀和 S,然后 O(N²) 枚举边长位 R 的正方形的右下角坐标 (i,j),即可通过上式 O(1) 计算出该正方形内所有目标的价值之和，更新答案。

样例代码

#include<iostream>
#include<cstdio>
using namespace std;
int f[5010][5010],n,m,r,c,x,y,z,i,j,ans;
int main()
{
    cin>>n>>m;
    r=c=m;
    for(i=1; i<=n; i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        x++,y++;
        f[x][y]+=z;
        r=max(r,x);
        c=max(c,y);
    }
    for(i=1; i<=r; i++)
        for(j=1; j<=c; j++)
            f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+f[i][j];
    for(i=m; i<=r; i++)
        for(j=m; j<=c; j++)
            ans=max(ans,f[i][j]-f[i][j-m]-f[i-m][j]+f[i-m][j-m]);
    cout<<ans<<endl;
    return 0;
}