[洛谷P2280][HNOI2003]激光炸弹[二维前缀和]

题面

本题的意义在于告诉你有二维前缀和这个东西, 不能再水了.

定义点(x,y)的二维前缀和S为: $$S[x,y]=\sum_{i=1}^{x}\sum_{j=1}^{y}a[i,j]$$

我们可以$latex O(N^2)$地递推出S数组: $latex S[x,y]=S[x-1,y]+S[x,y-1]-S[x-1][y-1]$(容斥的思想, 下面也是)

这样就可以$latex O(1)$求出任何子矩阵的和: 左上角为$latex (x_1,y_1)$, 右下角为$latex (x_2,y_2)$的子矩阵和为: $latex S[x_2,y_2]-S[x_1-1,y_2]-S[x_2,y_1-1]+S[x_1-1,y_1-1]$

 

#include<cstdio>
#define in inline
#define re register
in int read()
{
    int s(0),b(0);char ch;
    do{ch=getchar();if(ch=='-')b=1;}while(ch<'0'||ch>'9');
    while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    if(b) return -s;
    return s;
}
int n,r,s[5101][5101];
signed main()
{
    n=read(),r=read();
    for(re int i=1;i<=n;++i)
    {
        int x=read(),y=read();
        s[x+1][y+1]=read();//坐标统一+1防止越界, 写if太麻烦
    }
    for(re int i=1;i<=5001;++i)
        for(re int j=1;j<=5001;++j)
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+s[i][j];
    int ans=0;
    for(re int i=r;i<=5001;++i)
        for(re int j=r;j<=5001;++j)
            if(s[i][j]-s[i-r][j]-s[i][j-r]+s[i-r][j-r]>ans) ans=s[i][j]-s[i-r][j]-s[i][j-r]+s[i-r][j-r];
    printf("%d\n",ans);
    return 0;
}
赞(0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址