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

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误
HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误,它们的含义、原因和解决方法都有显著区别。以下是详细对比: 1. HTTP 406 (Not Acceptable) 含义: 客户端请求的内容类型与服务器支持的内容类型不匹…...

剑指offer20_链表中环的入口节点
链表中环的入口节点 给定一个链表,若其中包含环,则输出环的入口节点。 若其中不包含环,则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...
C++.OpenGL (10/64)基础光照(Basic Lighting)
基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...

Map相关知识
数据结构 二叉树 二叉树,顾名思义,每个节点最多有两个“叉”,也就是两个子节点,分别是左子 节点和右子节点。不过,二叉树并不要求每个节点都有两个子节点,有的节点只 有左子节点,有的节点只有…...

回溯算法学习
一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...

Linux中《基础IO》详细介绍
目录 理解"文件"狭义理解广义理解文件操作的归类认知系统角度文件类别 回顾C文件接口打开文件写文件读文件稍作修改,实现简单cat命令 输出信息到显示器,你有哪些方法stdin & stdout & stderr打开文件的方式 系统⽂件I/O⼀种传递标志位…...

ZYNQ学习记录FPGA(一)ZYNQ简介
一、知识准备 1.一些术语,缩写和概念: 1)ZYNQ全称:ZYNQ7000 All Pgrammable SoC 2)SoC:system on chips(片上系统),对比集成电路的SoB(system on board) 3)ARM:处理器…...

第一篇:Liunx环境下搭建PaddlePaddle 3.0基础环境(Liunx Centos8.5安装Python3.10+pip3.10)
第一篇:Liunx环境下搭建PaddlePaddle 3.0基础环境(Liunx Centos8.5安装Python3.10pip3.10) 一:前言二:安装编译依赖二:安装Python3.10三:安装PIP3.10四:安装Paddlepaddle基础框架4.1…...

《信号与系统》第 6 章 信号与系统的时域和频域特性
目录 6.0 引言 6.1 傅里叶变换的模和相位表示 6.2 线性时不变系统频率响应的模和相位表示 6.2.1 线性与非线性相位 6.2.2 群时延 6.2.3 对数模和相位图 6.3 理想频率选择性滤波器的时域特性 6.4 非理想滤波器的时域和频域特性讨论 6.5 一阶与二阶连续时间系统 6.5.1 …...
精益数据分析(98/126):电商转化率优化与网站性能的底层逻辑
精益数据分析(98/126):电商转化率优化与网站性能的底层逻辑 在电子商务领域,转化率与网站性能是决定商业成败的核心指标。今天,我们将深入解析不同类型电商平台的转化率基准,探讨页面加载速度对用户行为的…...