蓝桥杯好题推荐---激光炸弹

🌈个人主页：羽晨同学 

💫个人格言:“成为自己未来的主人~” 

题目链接

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;
}

 好了，今天的内容就到这里，我们明天再见。