洛谷P2280 激光炸弹

url: https://www.luogu.com.cn/problem/P2280

tag：
前缀和

思路：
这是一道二维前缀和。根据题意可以知道边长为m的爆破正方形最多可以破坏 m m 个目标，所以题目就变成了找到地图范围内，大小为m m的子矩阵中总价值最大的值。地图的范围可以直接定义成边界5000 5000，也可以像代码中的一样，一开始为m m表示至少要有一个子矩阵，之后每次读入一个新的目标时通过目标的坐标来更新地图大小。遍历每一个子矩阵可以通过从x = m和y = m开始遍历每一个点作为子矩阵的右下端点然后通过计算得到左上端点然后再通过二维前缀和的公式计算求最大值即可。

代码：

#include <iostream>
#include <cstring>
using namespace std;
const int N = 5010;
int p[N][N];
int n, m;
int nx, my;
int main()
{
    scanf("%d%d", &n, &m);
    nx = my = m;
    // 读数
    for (int i = 0; i < n; i ++)
    {
        int x, y, w;
        scanf("%d%d%d", &x, &y, &w);
        x ++, y ++;
        nx = max(x, nx), my = max(y, my);
        p[x][y] += w;
    }
    // 计算前缀和
    for (int i = 1; i <= nx; i ++)
        for (int j = 1; j <= my;  j++)
        {
            p[i][j] += p[i - 1][j] + p[i][j - 1] - p[i -1][j - 1];
        }
    // 求子矩阵中总价值最大的值
    int res =  -1;
    for (int i = m; i <= nx; i ++)
        for (int j = m; j <= my; j ++)
        {
            res = max(res, p[i][j] - p[i - m][j] - p[i][j - m] + p[i - m][j - m]);
        }
    cout << res <<endl;
    return 0;
}