题解 P2280 【[HNOI2003]激光炸弹】

陷语 · 2019-03-07 20:04:55 · 题解

激光炸弹

虽然我的题解也是前缀和，和大多数人都一样，不过按照人的思考惯性来说，我的这篇题解应该会更好理解一点吧

关于前缀和，我就不做太多赘述了，这大家都知道，楼上的一群dalao已经证明过了！

注意事项：

1.这道题卡你空间，所以对于这道题，你只要开一个数组s就行，读入的数据就直接往里面丢，这对求前缀和没有任何影响！对熟悉前缀和的人都知道，求前缀和只与前面的状态有关，大家可以花费1,2min证明一下，毕竟我们是OI选手，不求甚解是不可能的！！

2.x和y的数据范围都是>=0 这对我们的前缀和操作还是有一定影响的，为了避免出现数组越界的情况我们可以将“矩阵”整体右移1位，只需要在读入是写成s[x + 1][y + 1] = z就行了

3.这道题如果写的不小心的话，在求一个二维区间和的时候你的数组很有可能会越界，造成RE的情况！针对这种情况我直接写了一个特判233

附上代码：

#include <cstdio>

using namespace std;
const int N = 5005;

int s[N][N], n, r;
int x, y, z, ans;

inline int max(int x, int y) {return x > y? x : y;}

int main() {
//  freopen("in.txt", "r", stdin);

    scanf("%d %d", &n, &r);

    for(int i = 1; i <= n; ++i) {
        scanf("%d %d %d", &x, &y, &z);//read 
        s[x + 1][y + 1] = z;//将矩阵整体向右偏移 
    }

    for(int i = 1; i <= 5001; ++i)
        for(int j = 1; j <= 5001; ++j)
            s[i][j] = s[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];//前缀和提前计算每一个二维区间

    for(int i = 1; i <= 5001; ++i)
        for(int j = 1; j <= 5001; ++j) {
            x = i - r; y = j - r;//我自己写的特判 
            if(x < 0) x = 1;
            if(y < 0) y = 1;

            ans = max(ans, s[i][j] - s[x][j] - s[i][y] + s[x][y]);
        } 

    printf("%d\n", ans);
    return 0;
}