LG2280 [HNOI2003]激光炸弹

URL: 洛谷

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

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#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;
}