HNOI2003 激光炸弹

题面

link

solution

水题一枚，题目意思是给出n个点，每个点有一个价值，问一个边长为r的点最大能获得多大价值。

维护一个二维前缀和即可。

如果我们要求红色部分的和，是不是用整个有颜色部分的正方形的面积S - 黄色 - 绿色 - 蓝色

那么怎么利用前缀和的知识来求呢。

二维中，前缀和代表某点相对于矩阵左上角的矩形区域的面积。

所以可以推出ans = map[5][5]-map[5][5-2-1]-map[2][5-2-1]+map[2][2]这里为什么是5-2-1 呢， 5代表要求的点， 2代表边长

这道题有一个坑，就是边界上的点不算，所以我们要求边长为R-1的矩形.

code

送上AC代码

#include<stdio.h>
#include<iostream>
#include<math.h>
using namespace std;
int map[5005][5005]={0};
int main()
{
    int N,R;
    int x,y,w;
    cin>>N>>R;
    int n = R,m = R;
    for(int i=0;i<N;i++)
    {
        cin>>x>>y>>w;
        x++; y++;
        map[x][y]+=w;
        n = max(n,x);
        m = max(m,y);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            map[i][j] +=map[i-1][j]+map[i][j-1]-map[i-1][j-1];
        }
    }
    int ans = 0;
    for(int i=R;i<=n;i++)
    {
        for(int j=R;j<=m;j++)
        {
            int tmp = map[i][j]-map[i-R][j]-map[i][j-R]+map[i-R][j-R];
            ans = max(ans,tmp);
        }
    }
    cout<<ans<<endl;
 }