99. 激光炸弹（二维前缀和）

题目：

99. 激光炸弹 - AcWing题库

思路： 

1.矩形/正方形求最值--->二维前缀和

2.注意：此题不可开两个数组，空间会爆，前缀和数组与原数据数组共用一个数组。 

代码： 

#include 
#include 
#include 
 
using namespace std;
 
const int N = 5010;
 
int n, m;//目标横纵最大下标（避免遍历整个数组s[N][N],节约时间）
int s[N][N];
 
int main()
{
    int cnt, R;
    cin >> cnt >> R;
    R = min(5001, R);
 
    n = m = R;
    
    //输入
    while (cnt -- )
    {
        int x, y, w;
        cin >> x >> y >> w;
        x ++, y ++ ;
        n = max(n, x), m = max(m, y);
        s[x][y] += w;
    }
 
    // 预处理前缀和
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
 
    int res = 0;
 
    // 枚举所有边长是R的矩形，枚举(i, j)为右下角
    for (int i = R; i <= n; i ++ )
        for (int j = R; j <= m; j ++ )
            res = max(res, s[i][j] - s[i - R][j] - s[i][j - R] + s[i - R][j - R]);
 
    cout << res << endl;
 
    return 0;
}