激光炸弹 bzoj-1218 HNOI-2003

题目大意:在笛卡尔坐标系上有n个点,问一个平行于坐标轴的r*r的正方形可以最多覆盖多少个目标。

注释:$1\le n \le 10000$,$1\le answer\le 32767$。

想法:更一道水题。我们将所有的目标按坐标排序,之后暴力枚举。前缀和优化即可。

最后,附上丑陋的代码... ...

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 5010 
using namespace std;
int a[N+10][N+10];
int main()
{
    int n,r;
    cin >> n >> r ;
    for(int x,y,val,i=1;i<=n;i++)
    {
        scanf("%d%d%d",&x,&y,&val);
        a[x+1][y+1]+=val;
    }
 
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=N;j++)
        {
            a[i][j]+=a[i-1][j];
        }
    }
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=N;j++)
        {
            a[i][j]+=a[i][j-1];
        }
    }
    // puts("***");
    int ans=0xefefefef;
    for(int i=r;i<=N;i++)
    {
        for(int j=r;j<=N;j++)
        {
            ans=max(ans,a[i][j]-a[i-r][j]-a[i][j-r]+a[i-r][j-r]);
        }
    }
    printf("%d\n",ans);
    return 0;
}

小结:优化暴力是一种比较常见的解题手段。