最长递增子序列(51Nod - 1134)
2024-09-04 03:57:25
20180604 23:18
https://blog.csdn.net/joylnwang/article/details/6766317(写得很用心,膜拜dalao)
给出长度为N的数组,找出这个数组的最长递增子序列。(递增子序列是指,子序列的元素是递增的)
例如:5 1 6 8 2 4 5 10,最长递增子序列是1 2 4 5 10。
Input
第1行:1个数N,N为序列的长度(2 <= N <= 50000)
第2 - N + 1行:每行1个数,对应序列的元素(-10^9 <= S[i] <= 10^9)
Output
输出最长递增子序列的长度。
Input示例
8
5
1
6
8
2
4
5
10
Output示例
5
思路:(upper_bound and lower_bound)https://blog.csdn.net/Quack_quack/article/details/48447293
⒈仿佛为我打开了新世界大门,首先,用常规方法做回超时,嗯...所以先一个一个读取数字,因为是求的最长上升子序列,所以用STL里面的upper_bound直接把比原先在数组里的数大的后输入的数的坐标(?)传输给L,最后L的长度就是要求的最长上升子序列的值。
ps:代码是由学长提供(https://www.cnblogs.com/hua-dong/p/9133827.html)
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
using namespace std;
int a[];
int main()
{
int n,x,i,L=,pos=;
scanf("%d",&n);
for(i=;i<=n;i++){
scanf("%d",&x);
pos=upper_bound(a+,a+L+,x)-a;//格式啊.注意事项1.下标都是下标.
a[pos]=x;// 2.把数放进去,然后判断:如果x比现有的数都大pos返回的是L+1;
L=max(L,pos);// 3.但是运行到一半发现找到组织了(及x此时不是这一波中最大的数)那么x被淘汰.数组依旧长度为L(这是上一把的长度).
}
cout<<L<<endl;
return ;
}
给出长度为N的数组,找出这个数组的最长递增子序列。(递增子序列是指,子序列的元素是递增的)
例如:5 1 6 8 2 4 5 10,最长递增子序列是1 2 4 5 10。
Input第1行:1个数N,N为序列的长度(2 <= N <= 50000)
第2 - N + 1行:每行1个数,对应序列的元素(-10^9 <= Sii <= 10^9)Output输出最长递增子序列的长度。Sample Input
8
5
1
6
8
2
4
5
10
Sample Output
5
最新文章
- TypeScript 素描 - 接口
- elasticsearch 优化
- 编程模式之观察者模式(Observer)
- NopCommerce之事件通知
- $(function(){})和$(document).ready(function(){})
- c++学习笔记2(c++简单程序)
- Gridview中奇偶数行颜色设置
- Java 内存区域和GC机制-java概念理解
- android 签名被篡改(Keystore was tampered with, or password was incorrect)
- php多维数组按用户自定义顺序排序uasort()
- Perl解除引用:从引用还原到数据对象
- H5 40-CSS精灵图
- Intellij Idea免费激活方法(转)
- python的垃圾回收机制【转】
- vue中文章的折叠于显示全部
- Linux内核设计与实现(chapter1/2)
- 【POJ 3071】 Football(DP)
- python必须要安装的库
- 【WPF】树形结构TreeView的用法(MVVM)
- Android 对话框(Dialog)