[HNOI2003]激光炸弹

OJ题号：

BZOJ1218、洛谷2280

思路：

求出二维前缀和，然后DP。时间复杂度$O(n^2)$。
另外用扫描线+线段树可以达到$O(nlog n)$。

 1 #include<cstdio>
 2 #include<cctype>
 3 #include<algorithm>
 4 inline int getint() {
 5     char ch;
 6     while(!isdigit(ch=getchar()));
 7     int x=ch^'0';
 8     while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
 9     return x;
10 }
11 const int M=5002;
12 int m[M][M];
13 int main() {
14     int n=getint(),r=getint();
15     for(int i=1;i<=n;i++) {
16         int x=getint()+1,y=getint()+1,v=getint();
17         m[x][y]=v;
18     }
19     for(int i=1;i<M;i++) {
20         for(int j=1;j<M;j++) {
21             m[i][j]+=m[i-1][j]+m[i][j-1]-m[i-1][j-1];
22         }
23     }
24     int ans=0;
25     for(int i=r;i<M;i++) {
26         for(int j=r;j<M;j++) {
27             ans=std::max(ans,m[i][j]-m[i-r][j]-m[i][j-r]+m[i-r][j-r]);
28         }
29     }
30     printf("%d
",ans);
31     return 0;
32 }