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

补充二分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.kler.cn/a/587057.html

相关文章:

  • 【公务员考试】高效备考指南
  • 2018年全国职业院校技能大赛高职组-计算机网络应用竞赛竞赛样题F卷
  • 【C++】—— 一篇文章解决面试 继承菱形继承
  • A SURVEY ON POST-TRAINING OF LARGE LANGUAGE MODELS——大型语言模型的训练后优化综述——第一部分
  • 加密算法逆向与HOOK技术实战
  • OpenHarmony子系统开发 - ArkCompiler开发指导
  • matlab 控制系统GUI设计-PID控制超前滞后控制
  • 打靶日记Kioptix Level 4
  • vue项目如何实现条件查询?
  • 贪吃蛇小游戏-简单开发版
  • 【实战ES】实战 Elasticsearch:快速上手与深度实践-附录-2-性能调优工具箱
  • 路由器和网关支持边缘计算
  • 无需归一化的Transformers:神经网络设计的突破
  • 单元测试、系统测试、集成测试
  • MySQL数据库知识总结
  • Java 大视界 -- Java 大数据在智能金融资产定价与风险管理中的应用(134)
  • install of jenkins-2.501-1.1.noarch conflicts with file
  • 【redis】hash 类型应用场景
  • 面试系列|蚂蚁金服技术面【2】
  • The workbook already contains a sheet named