补充二分LIS

B3637 最长上升子序列

题目描述

这是一个简单的动规板子题。

给出一个由 n ( n ≤ 5000 ) n(n\le 5000) n(n5000) 个不超过 1 0 6 10^6 106 的正整数组成的序列。请输出这个序列的最长上升子序列的长度。

最长上升子序列是指,从原序列中按顺序取出一些数字排在一起,这些数字是逐渐增大的。

输入格式

第一行,一个整数 n n n,表示序列长度。

第二行有 n n n 个整数,表示这个序列。

输出格式

一个整数表示答案。

输入输出样例 #1

输入 #1

6
1 2 4 1 3 4

输出 #1

4

说明/提示

分别取出 1 1 1 2 2 2 3 3 3 4 4 4 即可。

#include<bits/stdc++.h>
using namespace std;
const int N = 5005;
int n,a[N],b[N];
int len = 1;
int j;
int find(int x){int l = 1,r = len,mid;while(l <= r){mid = (l+r)/2;if(x > b[mid])l = mid+1;else r = mid-1;}return l;
}
int main(){cin >> n;for(int i = 1;i<=n;i++)cin >> a[i];b[1] = a[1];for(int i = 2;i<=n;i++){if(a[i] > b[len]){b[++len] = a[i];}else{j = find(a[i]);b[j] = a[i];}}cout << len;return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/33975.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Redis实现高并发排行榜的功能

生活中排行榜是常见的功能&#xff0c;如游戏的排行榜&#xff0c;销售额的排行榜等等&#xff0c;排行榜不仅可以让用户有更多的激情参与到活动中来&#xff0c;而且可以更好的留存住用户&#xff0c;如下所示的拉新排行榜&#xff1a; 排行榜是一个常见的业务需求&#xff0…

数字孪生像魔镜,映照出无限可能的未来

在当今科技飞速发展的时代&#xff0c;数字孪生作为一项极具潜力的前沿技术&#xff0c;正逐渐崭露头角&#xff0c;成为众多领域关注的焦点。它犹如一面神奇的魔镜&#xff0c;以数字化的方式精准映照出现实世界中的各种实体与系统&#xff0c;为我们开启了一扇通往无限可能未…

每日一题---

深拷贝和浅拷贝的区别是什么&#xff1f; null 浅拷贝是指只复制对象本身和其内部的值类型字段&#xff0c;但不会复制对象内部的引用类型字段。换句话说&#xff0c;浅拷贝只是创建一个新的对象&#xff0c;然后将原对象的字段值复制到新对象中&#xff0c;但如果原对象内部有…

Chrome 扩展开发 API实战:Sessions (六)

1. 引言 chrome.sessions 是 Chrome 扩展开发者工具的一部分&#xff0c;提供了对最近关闭的标签页和窗口的访问&#xff0c;以及对会话恢复功能的支持。现代浏览器的一个显著特点是为用户提供更多的便利性&#xff0c;比如快速恢复意外关闭的页面。通过 chrome.sessions API&…

Spring Boot对接twilio发送邮件信息

要在Spring Boot应用程序中对接Twilio发送邮件信息&#xff0c;您可以使用Twilio的SendGrid API。以下是一个简单的步骤指南&#xff0c;帮助您完成这一过程&#xff1a; 1. 创建Twilio账户并获取API密钥 注册一个Twilio账户&#xff08;如果您还没有的话&#xff09;。在Twi…

学习15天:pytest

1、.pytest强大的插件 pytest-html(生成html格式的自动化测试报告) pytest-xdist测试用例分布式执行。多CPU分发。 pytest-ordering 用于改变测试用例的执行顺序 pytest-rerunfailures用例失败后重跑 allure-pytest 用于生成美观的测试报告。 2、规则&#xff1a; 模块…

Springboot+mybatis实现增删改查操作

继续写一下删除操作&#xff0c;删除有些不一样&#xff0c;首先在controller里面&#xff0c;我们需要改一下路由&#xff0c;我们后面要写/{id}传入路径参数&#xff0c;用PathVariable注解绑定id&#xff0c;剩下的都一样&#xff0c;传入id&#xff0c;然后写service和mapp…

Visual Studio里的调试(debugging)功能介绍

参考 1- Introduction to Debugging | Basic Visual Studio Debugging&#xff08;这是一位印度博主视频&#xff0c;我下面做到笔记也主要参考她的视频&#xff0c;但不得不说口音太重了&#xff0c;一股咖喱味&#xff09; 目录 个人对调试浅显的认识和对调试的介绍逐行调…

Java多线程与高并发专题——原子类和 volatile、synchronized 有什么异同?

原子类和 volatile异同 首先&#xff0c;通过我们对原子类和的了解&#xff0c;原子类和volatile 都能保证多线程环境下的数据可见性。在多线程程序中&#xff0c;每个线程都有自己的工作内存&#xff0c;当多个线程访问共享变量时&#xff0c;可能会出现一个线程修改了共享变…

c语言笔记 作用域

目录 作用域的基本概念 1.函数声明的作用域 2.局部变量的作用域 3.全局作用域 4.static修饰后的作用域 作用域的基本概念 在c语言中&#xff0c;我们的标志符是具有一定的可见范围的&#xff0c;我们称这个可见范围为作用域 在软件开发中&#xff0c;我们要确定好标识符的作…

MySQL数据库知识总结

MySQL数据库知识总结 一、基本概念及其介绍二、数据库中的数据类型&#xff08;一&#xff09;数值类型&#xff08;二&#xff09;字符串类型&#xff08;三&#xff09;日期类型 三、数据库基础语法&#xff08;一&#xff09;数据库的常用操作&#xff08;二&#xff09;数据…

SpaceSync智能排班:重构未来办公空间的神经中枢

文心智能体平台可免费使用DeepSeek 满血版啦&#xff0c;使用DeepSeek模型创建并提交智能体&#xff0c;即有机会瓜分万元奖金&#xff01;有这等好事还不快冲&#xff01; 文心智能体官网&#xff1a;文心智能体平台AgentBuilder | 想象即现实 本片文章为作者参加文心智能体平…

Blender-MCP服务源码3-插件开发

Blender-MCP服务源码3-插件开发 Blender-MCP服务源码解读-如何进行Blender插件开发 1-核心知识点 1&#xff09;使用Blender开发框架学习如何进行Blender调试2&#xff09;学习目标1-移除所有的Blender业务-了解如何MCP到底做了什么&#xff1f;3&#xff09;学习目标2-模拟MC…

每日一题---dd爱框框(Java中输入数据过多)

dd爱框框 实例&#xff1a; 输入&#xff1a; 10 20 1 1 6 10 9 3 3 5 3 7 输出&#xff1a; 3 5 这道题要解决Java中输入的数过多时&#xff0c;时间不足的的问题。 应用这个输入模板即可解决&#xff1a; Java中输入大量数据 import java.util.*; import java.io.*;pu…

Qlik Sense New Install with Restore

Background In case you meet the upgrade issue like us , you can follow the below step to recover the existing data to new installed Qlik Sense . Powered by Moshow郑锴-CSDN博客 please follow below steps: pgsql dump backupbackup table into sql by DBeaverst…

大数据-spark3.5安装部署之standalone模式

真实工作中还是要将应用提交到集群中去执行&#xff0c;Standalone模式就是使用Spark自身节点运行的集群模式&#xff0c;体现了经典的master-slave模式。集群共三台机器&#xff0c;具体如下 u22server4spark&#xff1a; master worker u22server4spark2&#xff1a; worke…

Uniapp 开发 App 端上架用户隐私协议实现指南

文章目录 引言一、为什么需要用户隐私协议&#xff1f;二、Uniapp 中实现用户隐私协议的步骤2.1 编写隐私协议内容2.2 在 Uniapp 中集成隐私协议2.3 DCloud数据采集说明2.4 配置方式3.1 Apple App Store3.2 Google Play Store 四、常见问题与解决方案4.1 隐私协议内容不完整4.2…

【C++】 —— 笔试刷题day_5

刷题day_5 一、游游的you 题目链接&#xff1a;游游的you 题目解析 题目要求&#xff1a; 输入a&#xff0c;b&#xff0c;c表示y、o、u三个字母的个数&#xff1b; 将这些字母连成字符串&#xff0c;并且这里you三个字母相邻获得2分&#xff0c;两个o字母相邻获得1分。 让我…

78. Harmonyos NEXT 懒加载数据源实现解析:BasicDataSource与CommonLazyDataSourceModel详解

温馨提示&#xff1a;本篇博客的详细代码已发布到 git : https://gitcode.com/nutpi/HarmonyosNext 可以下载运行哦&#xff01; Harmonyos NEXT 懒加载数据源实现解析&#xff1a;BasicDataSource与CommonLazyDataSourceModel详解 文章目录 Harmonyos NEXT 懒加载数据源实现解…

如何打包数据库mysql数据,并上传到虚拟机上进行部署?

1.连接数据库&#xff0c;使得我们能看到数据库信息&#xff0c;才能进行打包上传 2. 3. 导出结果如下&#xff0c;是xml文件 4.可以查询每个xml文件的属性&#xff0c;确保有大小&#xff0c;这样才是真实导出 5跟着黑马&#xff0c;新建文件夹&#xff0c;并且把对应的东西放…