激光炸弹

BZOJ

题意：一种新型的激光炸弹，可以摧毁一个边长为R的正方形内的所有的目标。现在地图上有n(N<=10000)个目标，用整数Xi,Yi(其值在[0,5000])表示目标在地图上的位置，每个目标都有一个价值。激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆破范围，即那个边长为R的正方形的边必须和x，y轴平行。若目标位于爆破正方形的边上，该目标将不会被摧毁。

分析：利用二位前缀和，先统计后查询。

//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
inline int read() {
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=5000;
int ans,s[N][N];
int main() {
    int n=read(),r=read();
    for(int i=1;i<=n;i++){
        int a=read(),b=read(),c=read();
        s[a][b]=c;
    }
    for(int i=0;i<5000;++i)
        for(int j=0;j<5000;++j){
            if(i-1>=0)s[i][j]+=s[i-1][j];
            if(j-1>=0)s[i][j]+=s[i][j-1];
            if(i-1>=0&&j-1>=0)s[i][j]-=s[i-1][j-1];
        }
    for(int i=0;i<5000;++i)
        for(int j=0;j<5000;++j){
            int cnt=s[i][j];
            if(i-r>=0)cnt-=s[i-r][j];
            if(j-r>=0)cnt-=s[i][j-r];
            if(i-r>=0&&j-r>=0)cnt+=s[i-r][j-r];
            ans=max(ans,cnt);
        }
    printf("%d\n",ans);
    return 0;
}

激光炸弹

原文：https://www.cnblogs.com/PPXppx/p/11227785.html