蓝桥杯好题推荐---激光炸弹
🌈个人主页:羽晨同学
💫个人格言:“成为自己未来的主人~”
题目链接
P2280 [HNOI2003] 激光炸弹 - 洛谷https://www.luogu.com.cn/problem/P2280
解题思路
在这道题目当中,我们使用的是二维前缀和数组的思想,我们首先可以常见一个二维前缀和数组和一个存放价值的数组。
#include <iostream>
using namespace std;
const int N = 5e3+10;
int f[N][N];//前缀和存放数组
int a[N][N];
然后,我们先对这个价值数组进行处理,由于后面使用的时候,我们是从(1,1)开始的,所以,我们统一把坐标往右下移动一位。
int n,m;cin>>n>>m;
//先把数据存放到价值的数组中
for(int i=1;i<=n;i++)
{
int x,y,v;cin>>x>>y>>v;
x++; y++;//使得下标从(1,1)开始
a[x][y]+=v;
}
此外,这里还有一个特别需要注意的点,就是题目中所同一个位置可能存放多个价值,所以,我们在进行价值处理的时候,应使用的是。
a[x][y]+=v;
然后,我们构建二维前缀和数组。
n = 5005;//确保可以找到全部的元素
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+a[i][j];
}
}
我们这里设置的将所有的数组的元素都包含在内。
然后,我们对每个边长的这个正方形进行遍历,确保它走过了所有的元素,然后获取最大值。
//遍历
int ret = 0;
m =min(m,n);
for(int x2=m;x2<=n;x2++)
{
for(int y2=m;y2<=n;y2++)
{
int x1 = x2-m+1; int y1 = y2-m+1;
ret = max(ret,f[x2][y2]-f[x1-1][y2]-f[x2][y1-1]+f[x1-1][y1-1]);
}
}
在这个之前,我们需要将m设置为m何n的最小值,因为这个正方形的边长是可能大于这个整个数组的长度的。
代码解决
#include <iostream>
using namespace std;
const int N = 5e3+10;
int f[N][N];//前缀和存放数组
int a[N][N];
int main()
{
int n,m;cin>>n>>m;
//先把数据存放到价值的数组中
for(int i=1;i<=n;i++)
{
int x,y,v;cin>>x>>y>>v;
x++; y++;//使得下标从(1,1)开始
a[x][y]+=v;
}
//构建二维前缀和数组
n = 5005;//确保可以找到全部的元素
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+a[i][j];
}
}
//遍历
int ret = 0;
m =min(m,n);
for(int x2=m;x2<=n;x2++)
{
for(int y2=m;y2<=n;y2++)
{
int x1 = x2-m+1; int y1 = y2-m+1;
ret = max(ret,f[x2][y2]-f[x1-1][y2]-f[x2][y1-1]+f[x1-1][y1-1]);
}
}
cout<<ret<<endl;
return 0;
}
好了,今天的内容就到这里,我们明天再见。