题解 P2280 [HNOI2003]激光炸弹

do_while_true · 2020-05-21 20:24:29 · 题解

upd: 增加了一点点解释 =w=

首先把问题化简一下，如果是一条线的话应该怎么办。

考虑到一个长度为 m 的线段最多可以覆盖到 m+1 个点，左右两端的点恰好与边重合。但是在此题中左右两端的点不能算，所以我们将这个边向两边任意一边移动小于 1 的一点点距离，就可以算上一边的端点。

也就是我们把这个投放的线段的两端放在不是整点数的位置，就能让一个长度为 m 的线段有效覆盖到 m 个点。

如图所示：

图画的有点丑

也就是说这个激光炸弹的投放的正方形的四个角不一定非得落在坐标轴的整数点位置，而是把这四个角放在格子的内部，这样恰好能覆盖到 m\cdot m 个点。

于是问题转化成了一个矩阵中大小为 m\cdot m 的子矩阵的最大价值，采用二维前缀和求解即可。

因为在题目中 0\leq x_i,y_i，所以 x_i,y_i 可能取值为 0，那么如果采用原坐标进行覆盖的话，在计算前缀和的时候会因为访问负数下标而造成RE的情况。所以可以特殊处理第 0 行以及第 0 列，或者直接按原坐标 +1 进行存储。

值得注意的是，如果选择按原坐标 +1 进行存储，则在枚举的范围应该到 5001 或者到最大的 x_i+1 和 y_i+1。否则在 (5000,5000) 的点是枚举不到的。

Code

#include<iostream>
#include<cstdio>
using namespace std;
int sum[5002][5002],n,m,x,y,v,ans;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&x,&y,&v);
        sum[x+1][y+1]+=v;
    }
    for(int i=1;i<=5001;i++)
        for(int j=1;j<=5001;j++)
            sum[i][j]+=sum[i][j-1]-sum[i-1][j-1]+sum[i-1][j];
    for(int i=m;i<=5001;i++)
        for(int j=m;j<=5001;j++)
            ans=max(ans,sum[i][j]-sum[i][j-m]-sum[i-m][j]+sum[i-m][j-m]);
    printf("%d",ans);
    return 0;
}