激光炸弹 bzoj1218
地图上有 Wi。
注意：不同目标可能在同一位置。
现在有一种新型的激光炸弹，可以摧毁一个包含 R×R 个位置的正方形内的所有的目标。
激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆炸范围，即那个正方形的边必须和x，y轴平行。
求一颗炸弹最多能炸掉地图上总价值为多少的目标。
输入格式
第一行输入正整数 R ,分别代表地图上的目标数目和正方形的边长，数据用空格隔开。
接下来y坐标和价值，数据用空格隔开。
输出格式
输出一个正整数，代表一颗炸弹最多能炸掉地图上目标的总价值数目。
数据范围
0≤Wi≤1000
输入样例：
2 1
0 0 1
1 1 1
输出样例：
1
对于这类边框不算包含的题，都可以选取 一条长和一条宽上 的算包含，说明：
对于两条宽上的点，则可以选择把框向上或向下 移动一点点，则一条宽上的点被包含进去，一条宽上的点在框外
对于两条长上的点，则可以选择把框向左或向右 移动一点点，则一条长上的点被包含进去，一条宽上的长在框外
所以 一条宽和一条长 上的点要算， 相当于左开右闭，上开下闭
为了方便，我们的框子还框整数，把长和宽分别 --，相当于把框子平移了一点点
对于前缀和可以通过 O（1）时间得到任何区间的值的和、积
暴力每个区间就行了
代码中的前缀和相减时， 减出来的区间不包含这个框子的上边上的点，也不包括右边上的点
坐标++，只是为了下表从1，开始
代码
1 #include<bits/stdc++.h> 2 using namespace std; 3 int f[5010][5010], n, m, r, c, ans; 4 int main(){ 5 scanf("%d%d", &n, &m); 6 r = c = m; // 初始炸弹轰炸范围 [0,m] 7 for(int i = 1; i <= n; ++ i) 8 { 9 int x, y, z; 10 scanf("%d%d%d",&x,&y,&z); 11 ++x, ++y, f[x][y]=z; 12 r = max(r, x), c = max(c, y); 13 } 14 for(int i = 1; i <= r; ++ i) 15 for(int j = 1; j <= c; ++ j) 16 f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + f[i][j]; 17 for(int i = m; i <= r; ++ i) 18 for(int j = m; j <= c; ++ j) 19 ans = max(ans, f[i][j] - f[i][j - m] - f[i - m][j] + f[i - m][j - m]); 20 printf("%d", ans); 21 return 0; 22 }