蓝桥杯算法题:蓝桥骑士
题目描述
小明是蓝桥王国的骑士,他喜欢不断突破自我。这天蓝桥国王给他安排了 N 个对手,他们的战力值分别为 a_1,a_2,…,a_n,且按顺序阻挡在小明的前方。对于这些对手小明可以选择挑战,也可以选择避战。
身为高傲的骑士,小明从不走回头路,且只愿意挑战战力值越来越高的对手。
请你算算小明最多会挑战多少名对手。
输入描述
输入第一行包含一个整数 N,表示对手的个数。第二行包含 N 个整数 a_1,a_2,…,a_n分别表示对手的战力值。
输出描述
输出仅一行包含一个整数表示答案。样例输入
6
1 4 2 2 5 6
样例输出
4
思路:本来是想用LIS动态规划来做的,但是不出意外超时了,LIS代码如下:
#include<bits/stdc++.h>
using namespace std;
int dp[400010];
int a[400010];
int main(){int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++){for(int j=0;j<i;j++){if(a[i]>a[j])dp[i]=max(dp[i],dp[j]+1);}}int maxN=0;for(int i=1;i<=n;i++){if(maxN<dp[i])maxN=dp[i];}cout<<maxN<<endl;
}
那怎么改进呢,比如说1 4 2 2,长度为2的子序列是不是有{1,4}和{1,2},如果以后出现一个数字5,LIS的做法是遍历1 4 2 2所有数字的值并dp出把5放进哪个子序列,它形成的序列最长。很明显是{1,4,5}或者{1,2,5},但是细想一下{1,4}跟{1,2}的长度是一样的,比4大的数字一定比2大,比2大的数字不一定比4大,那在长度一样的时候,我维护一个最小值就好了,用那个最小值来形成进一步的子序列。
代码如下,slln[i]=k表示长度i的子序列中,末尾的最小值是k:
#include<bits/stdc++.h>
using namespace std;
int a[400010];
int slln[400010];
int main(){int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}memset(slln,0x3f3f3f3f,sizeof(slln));slln[0]=0;int len=1;for(int i=1;i<=n;i++){for(int j=len-1;j>=0;j--){if(slln[j]<a[i]){slln[j+1]=min(slln[j+1],a[i]);if(j+1==len)len++;break;}}}cout<<len-1<<endl;
}
相关文章:
蓝桥杯算法题:蓝桥骑士
题目描述 小明是蓝桥王国的骑士,他喜欢不断突破自我。 这天蓝桥国王给他安排了 N 个对手,他们的战力值分别为 a_1,a_2,…,a_n,且按顺序阻挡在小明的前方。对于这些对手小明可以选择挑战,也可以选择避战。 身为高傲的骑士ÿ…...

sonar搭建(linux系统)
前景 静态代码扫描是CI/CD中重要的一环,可以在代码提交到代码仓库之后,在CI/CD流程中加入代码扫描步骤,从而及时地对代码进行质量的检查。这可以有效地降低后期维护成本,优化产品质量,提高产品交付速度。同时…...
中科软面试题
1、用户注册登录这一块用了哪些技术?数据库主要涉及那些表? 用了BCrypt加密算法,jwt生成token,网关实现全局过滤器校验token,还用了拦截器,获取在网关是指到请求头的userid存到threadlocal里面,…...

(五)PostgreSQL的管理工具pgAdmin
PostgreSQL的管理工具pgAdmin pgAdmin 是一款流行的开源图形界面管理工具,用于 PostgreSQL 数据库的管理和开发。它提供了一个易于使用的界面,允许用户执行各种数据库任务,如创建和修改数据库对象(表、视图、索引等)、…...

wsl 2在windows11上的设置
详细参考:Manual installation steps for older versions of WSL | Microsoft Learn 1.系统组件要打开 分别是:Hyper-V、虚拟机平台、适用于Windows的Linux子系统 2.以管理员方式运行命令行,逐步执行下面的命令 update to WSL 2, you must…...

常用API时间Arrays
常用API MATH 代表数学,是一个工具类,里面提供的都是对数据进行操作的一些静态方法。 方法名说明public static int abs(int a)获取参数绝对值public static double ceil(double a)向上取整public static double floor(double a)向下取整public stati…...
CentOS7.9.2009安装Kibana7.11.1
本文章使用CentOS7.9.2009服务器安装kibana7.11.1软件 1.服务器信息 [root@elasticsearch ~]# cat /etc/redhat-release CentOS Linux release 7.9.2009 (Core) [root@elasticsearch ~]# 2.kibana安装 2.1.创建kibana用户 创建kibana用户和组 命令: useradd kibana [r…...
Linux nfs 环境搭建
1.开发背景 nfs 即网络文件共享,主要通过 tcp、udp 等网络通讯的方式实现不同机器间的文件共享 2.开发需求 搭建 ubuntu 下的服务端,嵌入式开发板共享 ubuntu 的某个文件夹 3.开发环境 ubuntu20.04 嵌入式开发板 4.实现步骤 4.1 搭建 ubuntu 服务器…...

中移物联网 OneOS 操作系统环境搭建和工程创建
一、官网 OneOS Lite是中国移动针对物联网领域推出的轻量级操作系统,具有可裁剪、跨平台、低功耗、高安全等特点,支持ARM Cortex-A和 Cortex-M、MIPS、RISC-V等主流芯片架构,兼容POSIX、CMSIS等标准接口,支持Javascript、MicroPyt…...
AI技术创业机会之教育科技
教育科技领域正因人工智能(AI)技术的创新与发展而焕发全新活力,为创业者开辟了众多革新教育模式、提升教学效果的创业机会。以下详述了教育科技中AI技术的具体创业机会及其细节与内容,以助力有志于投身此领域的创业者全面了解市场前景与潜在机遇。 一、个性化学习平台 1.…...
【备战蓝桥杯】2024蓝桥杯赛前突击省一:图论模版篇
2024蓝桥杯赛前模版突击:图论篇 图论在蓝桥杯中一般考的不难,如果有图论的题,就基本是模板题,知道板子就有分了。 邻接表 本文使用方法1的方式实现邻接表 邻接表1 static int[] dist new int[N],st new int[N]; static int…...

GEE数据集——2019—2023年全球固定宽带和移动(蜂窝)网络性能(更新)
简介 全球固定宽带和移动(蜂窝)网络性能 全球固定宽带和移动(蜂窝)网络性能,分配给缩放级别 16 的网络 mercator 瓷砖(赤道处约 610.8 米乘 610.8 米)。数据以 Shapefile 格式和 Apache Parque…...
ChatGPT 写作秘籍:指导您如何利用ChatGPT撰写学术论文
ChatGPT无限次数:点击直达 ChatGPT 写作秘籍:指导您如何利用ChatGPT撰写学术论文 作为CSDN网站的作者,您可能经常面临不同类型的写作任务,包括学术论文的撰写。在这篇文章中,我们将探讨如何利用ChatGPT这一强大的文本生成工具来辅…...

【原创】springboot+mysql宠物管理系统设计与实现
个人主页:程序猿小小杨 个人简介:从事开发多年,Java、Php、Python、前端开发均有涉猎 博客内容:Java项目实战、项目演示、技术分享 文末有作者名片,希望和大家一起共同进步,你只管努力,剩下的交…...
Android app如何禁止运行在模拟器中
禁止 Android 应用程序在模拟器上运行涉及到在运行时检测应用是否在模拟器上运行,并根据情况做出相应的处理。以下是一种方法,通过判断设备的某些特征来检测模拟器: 创建一个用于检测模拟器的方法: public static boolean isEmu…...

libcurl 简单实用
LibCurl是一个开源的免费的多协议数据传输开源库,该框架具备跨平台性,开源免费,并提供了包括HTTP、FTP、SMTP、POP3等协议的功能,使用libcurl可以方便地进行网络数据传输操作,如发送HTTP请求、下载文件、发送电子邮件等…...

华为OD技术面试-有序数组第K最小值
背景 2024-03-15华为od 二面,记录结题过程 有序矩阵中第 K 小的元素 - 力扣(LeetCode) https://leetcode.cn/problems/kth-smallest-element-in-a-sorted-matrix/submissions/512483717/ 题目 给你一个 n x n 矩阵 matrix ,其…...

idea如何debug看springsecurity的过滤器顺序
idea如何debug看springsecurity的过滤器顺序 先配置一个Spring启动对象,后续需要根据这个对象来获取SpringSecurity的过滤器链 设置一个输出信息,需要在输出信息这里打上断点,才方便查看过滤器链 public static void main(String[] args) {//此时不…...

【力扣】125.验证回文串
刷题,过了真的好有成就感!!! 题解: 根据题目要求,我们需要处理一下几个问题: 将大写字母转变成小写对原来的字符串进行处理,只要字母和数字考虑只有一个和字符串为空的情况 1、将…...

Fantasy Map Creator 2
Fantasy Map Creator 2是一组风格化的图像,用于在图形编辑器中创建完整的彩色地图或游戏位置,无需艺术技能或图形平板电脑。 Fantasy Map Creator 2是一组风格化的图像,用于在图形编辑器中创建完整的彩色地图或游戏位置,无需艺术技能或图形平板电脑。 现在,每个人都可以在…...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?
编辑:陈萍萍的公主一点人工一点智能 未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战,在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...
在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能
下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能,包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...
【解密LSTM、GRU如何解决传统RNN梯度消失问题】
解密LSTM与GRU:如何让RNN变得更聪明? 在深度学习的世界里,循环神经网络(RNN)以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而,传统RNN存在的一个严重问题——梯度消失&#…...
python如何将word的doc另存为docx
将 DOCX 文件另存为 DOCX 格式(Python 实现) 在 Python 中,你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是,.doc 是旧的 Word 格式,而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...
今日科技热点速览
🔥 今日科技热点速览 🎮 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售,主打更强图形性能与沉浸式体验,支持多模态交互,受到全球玩家热捧 。 🤖 人工智能持续突破 DeepSeek-R1&…...

HashMap中的put方法执行流程(流程图)
1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中,其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下: 初始判断与哈希计算: 首先,putVal 方法会检查当前的 table(也就…...
scikit-learn机器学习
# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...

免费数学几何作图web平台
光锐软件免费数学工具,maths,数学制图,数学作图,几何作图,几何,AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...

(一)单例模式
一、前言 单例模式属于六大创建型模式,即在软件设计过程中,主要关注创建对象的结果,并不关心创建对象的过程及细节。创建型设计模式将类对象的实例化过程进行抽象化接口设计,从而隐藏了类对象的实例是如何被创建的,封装了软件系统使用的具体对象类型。 六大创建型模式包括…...

tauri项目,如何在rust端读取电脑环境变量
如果想在前端通过调用来获取环境变量的值,可以通过标准的依赖: std::env::var(name).ok() 想在前端通过调用来获取,可以写一个command函数: #[tauri::command] pub fn get_env_var(name: String) -> Result<String, Stri…...