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

信息学奥赛一本通——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 1i1<i2<...<iKN。比如,对于序列 ( 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(1N1000)。第二行给出序列中的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​&#xff0c;当 b 1 < b 2 < . . . < b S b_1<b_2<...<b_S b1​<b2​<...<bS​的时候&#xff0c;我们称这个序列是上升…...

vue3+antv x6自定义节点样式

先大致定下节点样式&#xff0c;需要展示标题&#xff0c;输入/输出连接桩&#xff0c; 参考样子大概是 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框架进行微信群组管理(一)

友情链接&#xff1a;geweapi.com 点击访问即可。 管理员操作 小提示&#xff1a; 添加、删除、转让多个wxid时仅限于添加/删除管理员&#xff0c;1添加 2删除 3转让 请求URL&#xff1a; http://域名地址/api/group/admin 请求方式&#xff1a; POST 请求头&#xff1a…...

【Linux】UDP协议——传输层

目录 传输层 再谈端口号 端口号范围划分 认识知名端口号 两个问题 netstat与iostat pidof UDP协议 UDP协议格式 UDP协议的特点 面向数据报 UDP的缓冲区 UDP使用注意事项 基于UDP的应用层协议 传输层 在学习HTTP等应用层协议时&#xff0c;为了便于理解&#xff…...

【Linux进阶之路】进程(上)

文章目录 前言一、操作系统加载过程二、进程1.基本概念2.基本信息①运行并观察进程②创建子进程③僵尸与孤儿进程&#xff08;父子进程衍生出来的问题&#xff09;1. 僵尸进程&#xff08;Zombie状态&#xff09;2. 孤儿进程 3.基本状态①操作系统的状态&#xff08;统一&#…...

爬虫018_urllib库_cookie反爬_post请求百度翻译获取百分翻译内容_以及详细翻译内容---python工作笔记037

然后我们来看如何用urllib发送post请求,这里我们 用百度翻译为例 我们翻译一个spider,然后我们看请求,可以看到有很多 找到sug这个 可以看到这里的form data,就是post请求体中的内容 然后我们点击preview其实就是 返回的实际内容 然后请求方式用的post 然后我们把上面的信息…...

【Nginx】Nginx网站服务

国外主流还是使用apache&#xff1b;国内现在主流是nginx&#xff08;并发能力强&#xff0c;相对稳定&#xff09; nginx&#xff1a;高新能、轻量级的web服务软件 特点&#xff1a; 1.稳定性高&#xff08;没apache稳&#xff09;&#xff1b; 2.系统资源消耗比较低&#xf…...

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 的概念、原理和具体使用。 作者&#xff1a;沈亚军 爱可生研发团队成员&#xff0c;负责公司 DMP 产品的后端开发&#xff0c;爱好太广&#xff0c;三天三夜都说不完&#xff0c;低调低调… 本文来源&#xff1a;原创投稿 爱可生开源社区出品&am…...

面部表情识别4:C++实现表情识别(含源码,可实时检测)

面部表情识别4&#xff1a;C实现表情识别(含源码&#xff0c;可实时检测) 目录 面部表情识别4&#xff1a;C实现表情识别(含源码&#xff0c;可实时检测) 1.面部表情识别方法 2.人脸检测方法 3.面部表情识别模型(Python) &#xff08;1&#xff09; 面部表情识别模型的训练…...

提升Element UI分页查询用户体验与交互:实现修改未保存提示

我实现的功能是在 element ui 的分页组件中进行分页查询时&#xff0c;如果当前有未保存的修改数据就提示用户&#xff0c;用户可以选择是否放弃未保存的数据。确认放弃就重新查询数据&#xff1b;选择不放弃&#xff0c;不重新查询&#xff0c;并且显示条数选择框保持原样&…...

UML-时序图

目录 时序图 时序图构成: 对象: 消息: 生命线(激活): 活动条: 时序图举例: 时序图 时序图也叫顺序图、序列图. 时序图描述按照时间的先后顺序对象之间的动作过程&#xff0c;是由生命线和消息组成 时序图构成: 对象: 对象是类的实例&#xff0c;对象是通过类来创建的&…...

Seata - 入门笔记

1、事务 访问并可能更新数据库中数据库中各种数据线的一个程序执行单元 原子性&#xff1a;事务是一个不可分割的工作单位&#xff0c;一个事务要么都做要么都不做 一致性&#xff1a;必须是使数据库从一个一致性到另一个一致性的状态&#xff0c;中间状态不能被观察到 隔离…...

springboot使用aop排除某些方法,更新从另外一张表,从另外一张表批量插入

AOP 在Spring Boot中使用AOP时&#xff0c;如果想要排除某些方法不被切面所影响&#xff0c;可以通过使用切面表达式中的!within关键字来实现。以下是一个示例&#xff1a; Aspect Component public class MyAspect {Before("execution(* com.example.service.*.*(..)) …...

Go 语言面试题(二):实现原理

文章目录 Q1 init() 函数是什么时候执行的&#xff1f;Q2 Go 语言的局部变量分配在栈上还是堆上&#xff1f;Q3 2 个 interface 可以比较吗&#xff1f;Q4 两个 nil 可能不相等吗&#xff1f;Q5 简述 Go 语言GC(垃圾回收)的工作原理Q6 函数返回局部变量的指针是否安全&#xff…...

SAP MM学习笔记16-在库品目评价

在库品目评价是指评估物料。具体比如物料价格&#xff0c;数量&#xff0c;保管场所等发生变化的时候&#xff0c;判断是否发生了变化&#xff0c;要不要生成 FI票&#xff0c;用哪个FI科目来进行管理等内容就叫在库品目评价。 在库品目评价有很多层级&#xff0c;这里先讲3兄弟…...

Azure通过自动化账户实现对资源变更

Azure通过自动化账户实现对资源变更 创建一个自动化账户第一种方式 添加凭据&#xff08;有更改资源权限的账户&#xff0c;没有auth认证情况&#xff09;创建一个Runbook&#xff0c;测试修改 AnalysisServices 定价层设置定时任务&#xff1a;开始定时任务&#xff1a; 第二种…...

使用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拉取或者提交代码时候&#xff0c;遇到了sourcetree报错&#xff1b; 排查了一会&#xff0c;比如查看了SSH keys是否有问题、是否与sourcetree账户状态有问题等等&#xff0c;最终才发现并解决问题 原因&#xff1a; 因为之前公司要求企业gitlab中…...

基于当前项目通过npm包形式暴露公共组件

1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹&#xff0c;并新增内容 3.创建package文件夹...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

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…...

ServerTrust 并非唯一

NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容

目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法&#xff0c;当前调用一个医疗行业的AI识别算法后返回…...

企业如何增强终端安全?

在数字化转型加速的今天&#xff0c;企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机&#xff0c;到工厂里的物联网设备、智能传感器&#xff0c;这些终端构成了企业与外部世界连接的 “神经末梢”。然而&#xff0c;随着远程办公的常态化和设备接入的爆炸式…...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)

Aspose.PDF 限制绕过方案&#xff1a;Java 字节码技术实战分享&#xff08;仅供学习&#xff09; 一、Aspose.PDF 简介二、说明&#xff08;⚠️仅供学习与研究使用&#xff09;三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...