首页 > 其他 > 详细

[二维前缀和] 激光炸弹

时间:2020-05-26 11:26:23      阅读:53      评论:0      收藏:0      [点我收藏+]

题意

炸弹可以摧毁边长为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

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!