题解 | #[HNOI2003]激光炸弹#

题意很明确，一个图中有些点有权值，求矩阵覆盖权值最大
很明显是二维前缀和，但是调了半天，细节还是要多考虑

#include<iostream>
using namespace std;
int a[6010][6010],sum[6610][6010];
int main()
{
    int n,r,ans=0;
    cin>>n>>r;
    r--;
    while(n--)
    {
        int x,y,v;
        cin>>x>>y>>v;
        a[x+1][y+1]=v;
    }
    for(int i=1;i<=5010;i++)
        for(int j=1;j<=5010;j++)
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];

    for(int i=1;i+r<=5010;i++)
        for(int j=1;j+r<=5010;j++)

            ans=max(ans,sum[i+r][j+r]-sum[i+r][j-1]-sum[i-1][j+r]+sum[i-1][j-1]);

    cout<<ans<<endl;
}