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

#include<bits/stdc++.h>
#include<iostream>
using namespace std;
int val[5010][5010]={0};
int main()
{
    int n,r;
    cin>>n>>r;
    int x_boundary = r;
    int y_boundary = r;
    for(int i=1,x,y,v;i<=n;i++)
    {
        cin>>x>>y>>v;
        val[++x][++y] = v;
        x_boundary = max(x,x_boundary);
        y_boundary = max(y,y_boundary);
    }
    for(int i=1;i<=x_boundary;i++)
    {
        for (int j=1;j<=y_boundary;j++)
        {
            val[i][j] = val[i-1][j]+val[i][j-1]+val[i][j]-val[i-1][j-1];
        }
    }
    int res = 0;
    for(int i=r;i<=x_boundary;i++)
    {
        for (int j=r;j<=y_boundary;j++)
        {
            res = max(res,val[i][j]-val[i][j-r]+val[i-r][j-r]-val[i-r][j]);
        }
    }    
    cout<<res;
    return 0;
}

本题重点是利用二维前缀和数组来求解 二维前缀和数组是由迭代的思想求得的。 困扰我很长时间的是题中若目标位于爆破正方形的边上，该目标将不会被摧毁 这句话。 这表面上使问题看起来更复杂了，但实际上在求的时候由于算式中各项均遵循这个原则，因此最终的影响相互抵消，导致没有影响，这也是为什么能用二维前缀和数组val[i][j]表示1到i行和1到j列的价值和。 而如何求出能框住最大价值的框呢？ 这还要回归到遍历框。而如何遍历框的问题归根到底是通过什么为根据来遍历框的问题。此处可以通过框的右上角来确定框的位置，再确定右上角点的移动范围即可实现遍历。思考可知，上图中五角星所指范围即是框右上角的移动范围。注意：上图最外层矩形是本题涉及的范围，此矩形右上角点坐标便是(x_boundary,y_boundary),即最大坐标的有价值点的坐标。

此题中我的一个理解是：每个矩形框上边和右边的点计入框内，左边和下边的点不计入框内（因为可以通过将框移动微小距离来使点入框），每个框的右上角点标识这个框及其信息，当所有框都遵循此规则时便符合逻辑。

同时如果要用val[i][j] = val[i-1][j]+val[i][j-1]+val[i][j]-val[i-1][j-1]来求二维前缀和，因为索引下标不为负数，因此将所有点横纵坐标均+1来避免此情况。