[codevs3955]最长严格上升子序列(加强版)
2024-08-31 12:46:55
题目大意:给你一个序列,要你求该序列中最长严格上升子序列的长度。
解题思路:此题算是一道LIS模板题。普通的$O(n^2)$的LIS是会TLE的,因为$n\le 1000000$,所以此题要用单调队列优化的LIS,时间复杂度$O(n\log n)$。
C++ Code:
#include<cstdio>
#include<algorithm>
using namespace std;
int n,k,q[1000005],a[1000005];
int main(){
k=0;
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
for(int i=1;i<=n;++i){
int p=lower_bound(q,q+k+1,a[i])-q-1;
//lower_bound(begin,end,val)的返回值是递增序列[begin,end)里第一个大于等于val的数的地址,我们要找的是小于val的数,所以最后要减一。
if(p==k)q[++k]=a[i];else
if(q[p+1]>a[i])q[p+1]=a[i];
}
printf("%d\n",k);
return 0;
}
最新文章
- FB
- WPF 创建自定义窗体
- 使用bee自动生成api文档
- Java中读取properties资源文件
- gridcontrol中使用右健菜单popupMenu1
- (medium)LeetCode 240.Search a 2D Matrix II
- JS之正则表达式验证URL
- 408. Valid Word Abbreviation
- google API的.NET库
- Js中执行变量中的命令语句,也就是所谓的宏替换(很实用的例子)
- Android-为何以及如何保存Fragment实例
- Tornado 模板支持“控制语句”和“表达语句”的表现形式
- 一个不错的PHP文件页面缓存类
- 初识java这个小姑娘(一)
- python入门(6)输入和输出
- LeetCode算法题-Design HashSet(Java实现)
- 移动web-bootstrap
- 如何在C#中引入CPLEX的dll(CPLEX系列-教程一)
- Spring+Quartz实现动态添加定时任务
- MySQL从删库到跑路_高级(一)——数据完整性
热门文章
- Codeforces Round #506 (Div. 3) A-C
- ECharts树图节点过多时取消缩放,调整容器高度自适应内容变化
- [读书笔记] Python数据分析 (一) 准备工作
- zabbbix4.0升级到4.2
- python 网络编程 粘包问题
- crm 系统项目(一) 登录,注册,校验
- 记一次BootStrap的使用
- Java 学习(10):java 异常处理
- Tokyo Tyrant(TTServer)系列(二)-启动參数和配置
- bzoj 1600 &;amp; Usaco 月赛 2008 建造栅栏 题解