当前位置: 首页 > article >正文

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

🌈个人主页:羽晨同学 

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

题目链接

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

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


http://www.kler.cn/a/588652.html

相关文章:

  • 【蓝桥杯每日一题】3.16
  • 【Agent】OpenManus 项目架构分析
  • 技术栈分享之----Swagger
  • 专题|Python贝叶斯金融数据应用实例合集:随机波动率SV模型、逻辑回归、参数更新、绩效比较BEST分析亚马逊股票、普尔指数...
  • 思维训练让你更高、更强 |【逻辑思维能力】「刷题训练笔记」假设法模式逻辑训练题(6-16)
  • JVM常用概念之即时常量
  • Bash语言的智能家居
  • airtest用法
  • 网络VLAN技术详解:原理、类型与实战配置
  • 重生之我在学Vue--第16天 Vue 3 插件开发
  • Django中的查询条件封装总结
  • 蓝桥杯——车牌(dfs全排列问题)
  • 【R语言入门】向量,存储和计算
  • Oracle Linux Server 7.9安装fail2ban
  • 【QA】建造者模式在Qt有哪些应用
  • Axure设计之动态折线图教程(中继器)
  • 微服务架构: SpringCloud实战案例
  • 基于CSV构建轻量级数据库:SQL与Excel操作的双模实践
  • SSL/TLS 1.2过程:Client端如何验证服务端证书?
  • 鸿蒙 @ohos.arkui.inspector (布局回调)