洛谷2280 [HNOI2003]激光炸弹

Luogu

分析

求出二维前缀和,然后大力枚举即可。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define re register
using namespace std;
int sum[5010][5010];
inline int read() //读入优化
{
    int X=0,w=1; char ch=0;
    while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();
    return X*w;
}
int main()
{
    int n,r,tx,ty,tv,ans=-1,k=0;
    n=read(); r=read();
    for (int i=1;i<=n;i++) sum[read()+1][read()+1]=read(); //输入,注意坐标要+1
    for (int i=1;i<=5001;i++)
        for (int j=1;j<=5001;j++)
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+sum[i][j]; //计算前缀和
    for (int i=0;i<=5001-r;i++)
        for (int j=0;j<=5001-r;j++) //枚举答案
        {
            k=sum[i+r][j+r]-sum[i+r][j]-sum[i][j+r]+sum[i][j];
            ans=max(k,ans);
        }
    printf("%d\n",ans); //输出
    return 0;
}
最后修改:2018 年 11 月 30 日 07 : 31 PM

发表评论