P2280 [HNOI2003]激光炸弹

题目描述

输入输出格式

输入格式：

输入文件名为input.txt

输入文件的第一行为正整数n和正整数R，接下来的n行每行有3个正整数，分别表示 xi，yi ，vi 。

输出格式：

输出文件名为output.txt

输出文件仅有一个正整数，表示一颗炸弹最多能炸掉地图上总价值为多少的目标（结果不会超过32767）。

输入输出样例

输入样例#1： 

2 1
0 0 1
1 1 1

输出样例#1： 

1

Solution：

　　题目特别水，很容易想到二维前缀和模拟一下就$OK$了。（但是我从$MLE$再到一直卡$90$分是什么鬼啊～）

　　二维前缀和套用容斥的思想，过程比较简单就不多说了，讲下坑点：1、注意不用开$long;long$，会爆空间。2、玄学地方是在循环中判断边界，不要在循环内判断边界（我也不知道为什么，反正我这样写死活$90$分）

代码：

#include<bits/stdc++.h>
#define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define il inline
#define ll long long
#define Max(a,b) ((a)>(b)?(a):(b))
using namespace std;
const int N=6000+7;
int n,r,x,y,z,a,b;
int s[N][N],ans=-2147483646;
il int gi(){
    int a=0;char x=getchar();bool f=0;
    while((x<'0'||x>'9')&&x!='-')x=getchar();
    if(x=='-')x=getchar(),f=1;
    while(x>='0'&&x<='9')a=(a<<3)+(a<<1)+x-48,x=getchar();
    return f?-a:a;
}
int main(){
    n=gi(),r=gi();
    For(i,1,n)x=gi(),y=gi(),a=Max(a,x),b=Max(b,y),s[x+1][y+1]=gi();
    For(i,1,5001) {
        For(j,1,5001)s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+s[i][j];
    }
    for(int i=0;i<=5000-r;i++) for(int j=0;j<=5000-r;j++){
        int p=i+r,q=j+r;
        ans=Max(s[p][q]+s[i][j]-s[i][q]-s[p][j],ans);
    }
    cout<<ans;
    return 0;
}