LG2280 [HNOI2003]激光炸弹

2019-07-23 10:24:52


题面描述:现在地图上有 $N$ 个目标,用整数 $x_i$ , $y_i$ 表示目标在地图上的位置,每个目标都有一个价值 $W_i$ 。求一颗炸弹最多能炸掉地图上总价值为多少的目标。

思路:求地图的二维前缀和,对每个点枚举,注意坐标中有0。

代码

#include<bits/stdc++.h>
using namespace std;
int n,r,s[5005][5005],ans=0;
int main(){
    cin>>n>>r;
    for(int i=1;i<=n;i++){
        int a,b,w;
        cin>>a>>b>>w;
        s[a+1][b+1]=w;
    }
    for(int i=1;i<=5002;i++){
        for(int j=1;j<=5002;j++){//使用二重循环计算二维前缀和
            s[i][j]=s[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
        }
    }
    for(int i=r;i<=5002;i++){
        for(int j=r;j<=5002;j++){//计算答案
            ans=max(ans,s[i][j]-s[i-r][j]-s[i][j-r]+s[i-r][j-r]);
        }
    }
    cout<<ans;
    return 0;
}