BZOJ1218:|BZOJ1218: [HNOI2003]激光炸弹
题意很好理解,在这里就不再叙述。
对于这道题,我们可以直接用二维前缀和来做
设f[i][j]表示从1,1到i,j这个矩形的总和
则有f[i][j] = f[i-1][j] + f[i][j-1] + x - f[i-1][j-1]
文章图片
对于所求矩形(即右下角黑色的),则如图所示用整个大矩形-两个红色的矩形+蓝色矩形。
【BZOJ1218:|BZOJ1218: [HNOI2003]激光炸弹】理解了二维前缀和
那么这道题就可以做了。
暴力枚举正方形右下角即可。
#include
#include
using namespace std;
int a[5002][5002];
int x,y,w;
int ans;
int main()
{
int n,r;
cin>>n>>r;
for(int i=1;
i<=n;
++i)
{
cin>>x>>y>>w;
a[x+1][y+1]=w;
}
for(int i=1;
i<=5001;
++i)
for(int j=1;
j<=5001;
++j)
a[i][j]=a[i-1][j]+a[i][j-1]+a[i][j]-a[i-1][j-1];
for(int i=0;
i<5001-r;
++i)
for(int j=0;
j<5001-r;
++j)
ans=max(ans,a[i+r][j+r]-a[i+r][j]-a[i][j+r]+a[i][j]);
cout
推荐阅读
- ROS|思岚rplidar A1激光点云数据读取
- ApolloStudio高手之路(12)(机器视觉图像匹配定位与激光打标领域深度结合(基于海康威视VisionMaster九点标定、模板快速匹配定位、标定转换以及金橙子E
- ApolloStudio高手之路(4)(用Python以最轻便的方式进行金橙子激光打标板卡二次开发(以EzCad2为载体二次开发))
- 关于IMU、激光雷达、Kinect的融合构想
- slam入门2(轮式里程计与2D激光联合标定及里程计内参校准)
- camsense X1 激光雷达的数据格式
- 用实际激光器发布数据的一些理解
- python|30分钟内基于激光雷达的手部姿态估计
- 算法|扫地机器人能有多硬核(好家伙自动驾驶、激光扫描、NLP这些硬科技全上了,科沃斯(技术创新才能打破行业内卷...))
- 快瞧!是哪些人把激光当“钥匙”