[二维前缀和] 激光炸弹

题意

炸弹可以摧毁边长为R的正方形内部的所有目标，不包括边，\(n\)个目标，每个目标有一个价值，爆炸范围必须与\(x，y\)轴平行，求正方形最大包含的价值数

预处理二维前缀和，从边长允许的范围内开始枚举，取最大值即可，题目要求不能将边上的计算，枚举\((R-1)\times (R-1)\)的正方形即可，认为在坐标系中所有点的坐标都+0.5

Code

#include<bits/stdc++.h>
using namespace std;
const int N=5100;
int n,r;
int s[N][N];
int max_x,max_y;
int main(){
    cin>>n>>r;
    max_x=max_y=r;
    while(n--){
        int x,y,w;
        cin>>x>>y>>w;
        x++;
        y++;
        s[x][y] +=w;
        max_x=max(x,max_x);
        max_y=max(y,max_y);
    }
    for(int i = 1; i <= max_x; i++)
        for(int j = 1; j <= max_y; j++)
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+s[i][j];
            
    int ans=0;
    for(int i = r; i <= max_x; i++)
        for(int j = r; j <= max_y; j++)
            ans=max(ans , s[i][j] - s[i-r][j] - s[i][j-r] + s[i-r][j-r]);
    cout<<ans<<endl;
}

[二维前缀和] 激光炸弹

原文：https://www.cnblogs.com/hhyx/p/12963799.html