99.激光炸弹

tip

原题链接：https://www.acwing.com/problem/content/101/

思路

前缀和一般可以用在某些求和类的问题上，特别是对于二维数组的求和，一般可以想到使用前缀和来求。

本题思路：

• 要去找一个 $R\times R$ 的子矩阵里面的和是很困难的，所以通过前缀和优化查找子矩阵的时间，$O(1)$ 就可以查找到对应的子矩阵。炸弹的范围本质上就是子矩阵的范围。
• 实际上就是用一个 $R\times R$ 的子矩阵扫描，找到这个范围内数值最大的数。

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 5e3 + 10;

int n, r;
int g[N][N];

int main() {
    int cnt;
    cin >> cnt >> r;
    r = min(5001, r);
    
    int n = r, m = r;
    for (int i = 0; i < cnt; i++) {
        int x, y, w;
        cin >> x >> y >> w;
        x++, y++;
        n = max(n, x), m = max(m, y);
        g[x][y] += w;
    }
    
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            g[i][j] += g[i][j - 1] + g[i - 1][j] - g[i - 1][j - 1];
    
    int res = 0;
    for (int i = r; i <= n; i++) {
        for (int j = r; j <= m; j++) {
            res = max(res, g[i][j] - g[i - r][j] - g[i][j - r] + g[i - r][j - r]);
        }
    }
    cout << res << endl;
    
    return 0;
}