当前位置: 首页 > 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中…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

Frozen-Flask :将 Flask 应用“冻结”为静态文件

Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是&#xff1a;将一个 Flask Web 应用生成成纯静态 HTML 文件&#xff0c;从而可以部署到静态网站托管服务上&#xff0c;如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序

一、开发环境准备 ​​工具安装​​&#xff1a; 下载安装DevEco Studio 4.0&#xff08;支持HarmonyOS 5&#xff09;配置HarmonyOS SDK 5.0确保Node.js版本≥14 ​​项目初始化​​&#xff1a; ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

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

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

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文全面剖析RNN核心原理&#xff0c;深入讲解梯度消失/爆炸问题&#xff0c;并通过LSTM/GRU结构实现解决方案&#xff0c;提供时间序列预测和文本生成…...