信息学奥赛一本通——1281:最长上升子序列
文章目录
- 题目
- 【题目描述】
- 【输入】
- 【输出】
- 【输入样例】
- 【输出样例】
- AC代码
题目
【题目描述】
一个数的序列 b i b_i bi,当 b 1 < b 2 < . . . < b S b_1<b_2<...<b_S b1<b2<...<bS的时候,我们称这个序列是上升的。对于给定的一个序列 ( a 1 , a 2 , . . . , a N ) (a_1,a_2,...,a_N) (a1,a2,...,aN),我们可以得到一些上升的子序列 ( a i 1 , a i 2 , . . . , a i K ) (a_{i1},a_{i2},...,a_{iK}) (ai1,ai2,...,aiK),这里 1 ≤ i 1 < i 2 < . . . < i K ≤ N 1≤i_1<i_2<...<i_K≤N 1≤i1<i2<...<iK≤N。比如,对于序列 ( 1 , 7 , 3 , 5 , 9 , 4 , 8 ) (1,7,3,5,9,4,8) (1,7,3,5,9,4,8),有它的一些上升子序列,如 ( 1 , 7 ) , ( 3 , 4 , 8 ) (1,7),(3,4,8) (1,7),(3,4,8)等等。这些子序列中最长的长度是4,比如子序列 ( 1 , 3 , 5 , 8 ) (1,3,5,8) (1,3,5,8)。
你的任务,就是对于给定的序列,求出最长上升子序列的长度。
【输入】
输入的第一行是序列的长度 N ( 1 ≤ N ≤ 1000 ) N(1≤N≤1000) N(1≤N≤1000)。第二行给出序列中的N个整数,这些整数的取值范围都在 0 0 0~ 10000 10000 10000。
【输出】
最长上升子序列的长度。
【输入样例】
7
1 7 3 5 9 4 8
【输出样例】
4
AC代码
#include<bits/stdc++.h>
using namespace std;
int n,a[1145],f[1145],i,j,ans=1;
int main() {cin>>n;for(i=1;i<=n;i++) {cin>>a[i];}for(i=1;i<=n;i++) {f[i]=1;}for(i=1;i<=n;i++) {for(j=1;j<i;j++) {if(a[i]>a[j]) {f[i]=max(f[j]+1,f[i]);}}ans=max(ans,f[i]);}cout<<ans;return 0;
}
相关文章:
信息学奥赛一本通——1281:最长上升子序列
文章目录 题目【题目描述】【输入】【输出】【输入样例】【输出样例】 AC代码 题目 【题目描述】 一个数的序列 b i b_i bi,当 b 1 < b 2 < . . . < b S b_1<b_2<...<b_S b1<b2<...<bS的时候,我们称这个序列是上升…...
vue3+antv x6自定义节点样式
先大致定下节点样式,需要展示标题,输入/输出连接桩, 参考样子大概是 https://x6.antv.antgroup.com/examples/showcase/practices#class 这是根据antv x6配置 非自定义节点 图表案例 结果 数据格式大概是 nodes:[{title:鸟,id:node1,ports…...
Arcgis中直接通过sde更新sqlserver空间数据库失败
问题 背景 不知道有没有人经历过这样一个情况,我们直接在Arcgis中通过sde更新serserver数据库会失败,就是虽然在sde更新sqlserver数据库,但是在Navicat中通过sql语句来查询,发现数据并没有更新,如:上图中,更新数据库后,第一张图是sde打开的sqlserver数据库,它的数据库…...
使用gewe框架进行微信群组管理(一)
友情链接:geweapi.com 点击访问即可。 管理员操作 小提示: 添加、删除、转让多个wxid时仅限于添加/删除管理员,1添加 2删除 3转让 请求URL: http://域名地址/api/group/admin 请求方式: POST 请求头:…...
【Linux】UDP协议——传输层
目录 传输层 再谈端口号 端口号范围划分 认识知名端口号 两个问题 netstat与iostat pidof UDP协议 UDP协议格式 UDP协议的特点 面向数据报 UDP的缓冲区 UDP使用注意事项 基于UDP的应用层协议 传输层 在学习HTTP等应用层协议时,为了便于理解ÿ…...
【Linux进阶之路】进程(上)
文章目录 前言一、操作系统加载过程二、进程1.基本概念2.基本信息①运行并观察进程②创建子进程③僵尸与孤儿进程(父子进程衍生出来的问题)1. 僵尸进程(Zombie状态)2. 孤儿进程 3.基本状态①操作系统的状态(统一&#…...
爬虫018_urllib库_cookie反爬_post请求百度翻译获取百分翻译内容_以及详细翻译内容---python工作笔记037
然后我们来看如何用urllib发送post请求,这里我们 用百度翻译为例 我们翻译一个spider,然后我们看请求,可以看到有很多 找到sug这个 可以看到这里的form data,就是post请求体中的内容 然后我们点击preview其实就是 返回的实际内容 然后请求方式用的post 然后我们把上面的信息…...
【Nginx】Nginx网站服务
国外主流还是使用apache;国内现在主流是nginx(并发能力强,相对稳定) nginx:高新能、轻量级的web服务软件 特点: 1.稳定性高(没apache稳); 2.系统资源消耗比较低…...
go语言从0基础到安全项目开发实战
一.环境搭建并helloworld 搭建环境比较简单 1.1安装SDK 到以下链接下 Go下载 - Go语言中文网 - Golang中文社区 下载windows版本64位zip包 https://studygolang.com/dl/golang/go1.20.7.windows-amd64.zip 1.2配置环境变量 不配置的话就只能在bin目录下才能运行go命令 …...
Kubernetes Service 工作原理
本文介绍了 Kubernetes Service 的概念、原理和具体使用。 作者:沈亚军 爱可生研发团队成员,负责公司 DMP 产品的后端开发,爱好太广,三天三夜都说不完,低调低调… 本文来源:原创投稿 爱可生开源社区出品&am…...
面部表情识别4:C++实现表情识别(含源码,可实时检测)
面部表情识别4:C实现表情识别(含源码,可实时检测) 目录 面部表情识别4:C实现表情识别(含源码,可实时检测) 1.面部表情识别方法 2.人脸检测方法 3.面部表情识别模型(Python) (1) 面部表情识别模型的训练…...
提升Element UI分页查询用户体验与交互:实现修改未保存提示
我实现的功能是在 element ui 的分页组件中进行分页查询时,如果当前有未保存的修改数据就提示用户,用户可以选择是否放弃未保存的数据。确认放弃就重新查询数据;选择不放弃,不重新查询,并且显示条数选择框保持原样&…...
UML-时序图
目录 时序图 时序图构成: 对象: 消息: 生命线(激活): 活动条: 时序图举例: 时序图 时序图也叫顺序图、序列图. 时序图描述按照时间的先后顺序对象之间的动作过程,是由生命线和消息组成 时序图构成: 对象: 对象是类的实例,对象是通过类来创建的&…...
Seata - 入门笔记
1、事务 访问并可能更新数据库中数据库中各种数据线的一个程序执行单元 原子性:事务是一个不可分割的工作单位,一个事务要么都做要么都不做 一致性:必须是使数据库从一个一致性到另一个一致性的状态,中间状态不能被观察到 隔离…...
springboot使用aop排除某些方法,更新从另外一张表,从另外一张表批量插入
AOP 在Spring Boot中使用AOP时,如果想要排除某些方法不被切面所影响,可以通过使用切面表达式中的!within关键字来实现。以下是一个示例: Aspect Component public class MyAspect {Before("execution(* com.example.service.*.*(..)) …...
Go 语言面试题(二):实现原理
文章目录 Q1 init() 函数是什么时候执行的?Q2 Go 语言的局部变量分配在栈上还是堆上?Q3 2 个 interface 可以比较吗?Q4 两个 nil 可能不相等吗?Q5 简述 Go 语言GC(垃圾回收)的工作原理Q6 函数返回局部变量的指针是否安全ÿ…...
SAP MM学习笔记16-在库品目评价
在库品目评价是指评估物料。具体比如物料价格,数量,保管场所等发生变化的时候,判断是否发生了变化,要不要生成 FI票,用哪个FI科目来进行管理等内容就叫在库品目评价。 在库品目评价有很多层级,这里先讲3兄弟…...
Azure通过自动化账户实现对资源变更
Azure通过自动化账户实现对资源变更 创建一个自动化账户第一种方式 添加凭据(有更改资源权限的账户,没有auth认证情况)创建一个Runbook,测试修改 AnalysisServices 定价层设置定时任务:开始定时任务: 第二种…...
使用luarocks安装cjson并使用cjson
1.luarocks安装 wget https://luarocks.org/releases/luarocks-3.3.1.tar.gz --no-check-certificatels -lrthtar -xvf luarocks-3.3.1.tar.gz mv luarocks-3.3.1 /usr/local/cd /usr/local/luarocks-3.3.1/./configure --prefix/usr/local/luarocks-3.3.1 vim /etc/profilePAT…...
【已解决】mac端 sourceTree 解决remote: HTTP Basic: Access denied报错
又是在一次使用sourcetree拉取或者提交代码时候,遇到了sourcetree报错; 排查了一会,比如查看了SSH keys是否有问题、是否与sourcetree账户状态有问题等等,最终才发现并解决问题 原因: 因为之前公司要求企业gitlab中…...
基于大模型的 UI 自动化系统
基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...
蓝桥杯 2024 15届国赛 A组 儿童节快乐
P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡,轻快的音乐在耳边持续回荡,小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下,六一来了。 今天是六一儿童节,小蓝老师为了让大家在节…...
P3 QT项目----记事本(3.8)
3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...
【配置 YOLOX 用于按目录分类的图片数据集】
现在的图标点选越来越多,如何一步解决,采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集(每个目录代表一个类别,目录下是该类别的所有图片),你需要进行以下配置步骤&#x…...
智能AI电话机器人系统的识别能力现状与发展水平
一、引言 随着人工智能技术的飞速发展,AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术,在客户服务、营销推广、信息查询等领域发挥着越来越重要…...
Mysql中select查询语句的执行过程
目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析(Parser) 2.4、执行sql 1. 预处理(Preprocessor) 2. 查询优化器(Optimizer) 3. 执行器…...
【LeetCode】3309. 连接二进制表示可形成的最大数值(递归|回溯|位运算)
LeetCode 3309. 连接二进制表示可形成的最大数值(中等) 题目描述解题思路Java代码 题目描述 题目链接:LeetCode 3309. 连接二进制表示可形成的最大数值(中等) 给你一个长度为 3 的整数数组 nums。 现以某种顺序 连接…...
苹果AI眼镜:从“工具”到“社交姿态”的范式革命——重新定义AI交互入口的未来机会
在2025年的AI硬件浪潮中,苹果AI眼镜(Apple Glasses)正在引发一场关于“人机交互形态”的深度思考。它并非简单地替代AirPods或Apple Watch,而是开辟了一个全新的、日常可接受的AI入口。其核心价值不在于功能的堆叠,而在于如何通过形态设计打破社交壁垒,成为用户“全天佩戴…...
Ubuntu系统复制(U盘-电脑硬盘)
所需环境 电脑自带硬盘:1块 (1T) U盘1:Ubuntu系统引导盘(用于“U盘2”复制到“电脑自带硬盘”) U盘2:Ubuntu系统盘(1T,用于被复制) !!!建议“电脑…...
MFE(微前端) Module Federation:Webpack.config.js文件中每个属性的含义解释
以Module Federation 插件详为例,Webpack.config.js它可能的配置和含义如下: 前言 Module Federation 的Webpack.config.js核心配置包括: name filename(定义应用标识) remotes(引用远程模块࿰…...
