蓝桥杯算法题:蓝桥骑士
题目描述
小明是蓝桥王国的骑士,他喜欢不断突破自我。这天蓝桥国王给他安排了 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是一组风格化的图像,用于在图形编辑器中创建完整的彩色地图或游戏位置,无需艺术技能或图形平板电脑。 现在,每个人都可以在…...

基于FPGA的PID算法学习———实现PID比例控制算法
基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容:参考网站: PID算法控制 PID即:Proportional(比例)、Integral(积分&…...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...

AI Agent与Agentic AI:原理、应用、挑战与未来展望
文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例:使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例:使用OpenAI GPT-3进…...

高频面试之3Zookeeper
高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个?3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制(过半机制࿰…...

Python实现prophet 理论及参数优化
文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候,写过一篇简单实现,后期随着对该模型的深入研究,本次记录涉及到prophet 的公式以及参数调优,从公式可以更直观…...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放
简介 前面两期文章我们介绍了I2S的读取和写入,一个是通过INMP441麦克风模块采集音频,一个是通过PCM5102A模块播放音频,那如果我们将两者结合起来,将麦克风采集到的音频通过PCM5102A播放,是不是就可以做一个扩音器了呢…...
关于 WASM:1. WASM 基础原理
一、WASM 简介 1.1 WebAssembly 是什么? WebAssembly(WASM) 是一种能在现代浏览器中高效运行的二进制指令格式,它不是传统的编程语言,而是一种 低级字节码格式,可由高级语言(如 C、C、Rust&am…...
【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具
第2章 虚拟机性能监控,故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令:jps [options] [hostid] 功能:本地虚拟机进程显示进程ID(与ps相同),可同时显示主类&#x…...

视觉slam十四讲实践部分记录——ch2、ch3
ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...

GruntJS-前端自动化任务运行器从入门到实战
Grunt 完全指南:从入门到实战 一、Grunt 是什么? Grunt是一个基于 Node.js 的前端自动化任务运行器,主要用于自动化执行项目开发中重复性高的任务,例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...