P2280 [HNOI2003]激光炸弹 题解

· · 题解

早上做到一道 超级毒瘤 的题目！！

传送门：P2280 [HNOI2003]激光炸弹

看到这道题目，算法就很明显地展现在我们眼前：前缀和（只不过是二维的）！【题目已经说得很清楚了，这里就不再重复了】

对于这道题，我们可以开一个二维数组：f[i][j] ，表示以 (i,j) 作为右下角的矩形的总价值，那我们就可以很快地推出状态转移方程：

\large f[i][j]+=f[i-1][j]+f[i][j-1]-f[i-1][j-1] 最后统计时，我们就可以枚举以 $R$ 为边长的正方形的右下角进行计算，转移方程也可以很快地推出来： $$ \large ans=max\{f[i][j]-f[i-r][j]-f[i][j-r]+f[i-r][j-r]\} $$ 然后就有这个代码了： ```cpp #include <bits/stdc++.h> #define M 5010 #define int long long using namespace std; int f[M][M]; int n, m, r, ans; inline int read() { int re=0, f=1; char ch=getchar(); while(ch<'0' || ch>'9') {if(ch=='-') f=-1; ch=getchar();} while(ch>='0' && ch<='9') {re=re*10+(ch-'0'); ch=getchar();} return re*f; } signed main() { n=read(); r=read(); for(int i=1;i<=n;++i) { int x=read(), y=read(), z=read(); f[x+1][y+1]=z; //题目中是从点(0,0)开始计算的，为了使代码实现起来更方便，我们就以点(1,1)作为起始节点 //也就是原本节点(x,y)变成了(x+1,y+1) } for(int i=1;i<=n+1;++i) for(int j=1;j<=n+1;++j) f[i][j]+=f[i-1][j]+f[i][j-1]-f[i-1][j-1]; ans=0; for(int i=r;i<=n+1;++i) for(int j=r;j<=n+1;++j) ans=max(ans,f[i][j]-f[i-r][j]-f[i][j-r]+f[i-r][j-r]); printf("%lld\n",ans); return 0; } ``` 可结果呢：······ ![](https://i.bmp.ovh/imgs/2019/08/12be519f4c8b95ea.png) ### 以下是重点细节：：： 题目中给出的数据范围是： $$ \large 0\le x_i,y_i\le5000 $$ 而我这里开的是 **long long** 不爆才怪！ 然后我就开始了我~~漫长的~~改题之旅 $qwq

这时，我又重新看了一下题目·······

这里的 n 是指目标的个数，但不是这个棋盘的面积！！！

所以上面的代码哪里写错了，就一目了然了~

for(int i=r;i<= /*n*/ 5001;++i)
  for(int j=r;j<= /*n*/ 5001;++j)
    ans=max(ans,f[i][j]-f[i-r][j]-f[i][j-r]+f[i-r][j-r]);

现在就对了呀（F***）附上c++代码

#include <bits/stdc++.h>
#define M 5100
using namespace std;

int f[M][M];
int n, m, r, ans;

inline int read()
{
    int re=0, f=1; char ch=getchar();
    while(ch<'0' || ch>'9') {if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0' && ch<='9') {re=re*10+(ch-'0'); ch=getchar();}
    return re*f;
}

int main()
{
    n=read(); r=read();
    for(int i=1;i<=n;++i)
    {
        int x=read(), y=read(), z=read();
        f[x+1][y+1]=z;
    }
    for(int i=1;i<=5001;++i)
      for(int j=1;j<=5001;++j)
        f[i][j]+=f[i-1][j]+f[i][j-1]-f[i-1][j-1];
    ans=0;
    for(int i=r;i<=5001;++i)
      for(int j=r;j<=5001;++j)
        ans=max(ans,f[i][j]-f[i-r][j]-f[i][j-r]+f[i-r][j-r]);
    printf("%d\n",ans);
    return 0;
}