最长上升序列(Lis)
2024-08-23 09:15:17
Description
A numeric sequence of ai is ordered if a1 < a2 < ... < aN. Let the subsequence of the given numeric sequence (a1, a2, ..., aN) be any sequence (ai1, ai2, ..., aiK), where 1 <= i1 < i2 < ... < iK <= N. For example, the sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, e.g., (1, 7), (3, 4, 8) and many others. All longest ordered subsequences of this sequence are of length 4, e.g., (1, 3, 5, 8).
Your program, when given the numeric sequence, must find the length of its longest ordered subsequence.
给出一个长度为N的数字串,找出一个严格上升的数字序列来.
Your program, when given the numeric sequence, must find the length of its longest ordered subsequence.
给出一个长度为N的数字串,找出一个严格上升的数字序列来.
Input
The first line of input contains the length of sequence N (1 <= N <= 1000). The second line contains the elements of sequence - N integers in the range from 0 to 10000 each, separated by spaces.
Output
Output must contain a single integer - the length of the longest ordered subsequence of the given sequence.
Sample Input
7
1 7 3 5 9 4 8
Sample Output
4
这道题对于现在的我来说已经算是水题了,但是当年我还是看了半个小时才看懂。
f[i]表示到i最长的上升序列
主要的思路就是枚举每个点,然后再与后面的点比较,加入后面的点比他大,长度就+1,即f[j]>f[i],f[j]=f[i]+1;(当然前提是f[i]+1要比原本的f[j]要大)
代码:
#include<cstdio>
#include<algorithm>
using namespace std;
int s[],n,a[],ans;
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
s[i]=;
}
for(int i=;i<=n;i++)
for(int j=i+;j<=n;j++)
if(a[i]<a[j]&&s[i]+>=s[j])s[j]=s[i]+,ans=max(ans,s[j]);
printf("%d",ans);
}
这是O(N^2)的算法,当数据大一些的时候就不行了。
众所皆知,大多数O(N^2)的算法可以用二分优化到O(N log(N))。
没错,就是我们可以用一个数组来存,但是这个数组存的并不是答案,只是当前形成的上升序列,每进来一个数,都用二分查找第一个比他小的数,然后取而代之,如果没有比他小的数,就放到最后面,数组最后的元素个数就是答案。
代码:
#include<bits/stdc++.h>
using namespace std;
int f[];
int t,m,n;
int main()
{
int m;
cin>>m;
for(int i=;i<=m;i++)
{
int ans=;
cin>>n;
for(int i=;i<=n;i++)
{ cin>>t;
if(i==) f[++ans]=t;
else
{
if(t>f[ans]) f[++ans]=t;
else
{
int x=lower_bound(f+,f+ans,t)-f;
f[x]=t;
}
}
}
cout<<ans<<endl;
}
return ;
}
其实还有树状数组的做法,这里不给出了
最新文章
- 结合ABP源码实现邮件发送功能
- wordpress和普通网页如何使用百度分享组件
- fastcgi安装
- Emacs配置文件
- win7和ubuntu双系统删除ubuntu的方法
- IOS开发-第三方SDWebImage下载网络图片的使用
- SVN服务器搭建和使用(三)(转载)
- 十、Notepad++正则表达式使用
- 误差逆传播(error BackPropagation, BP)算法推导及向量化表示
- Miller-Rabin质数测试
- 【甘道夫】Win7x64环境下编译Apache Hadoop2.2.0的Eclipse小工具
- (c#)SKYPE API项目总结(一)
- OpenVPN CentOS7 安装部署配置详解
- A-Text Reverse(文本反向读)
- 【python练习题】程序1
- JavaEE-Servlet的部署和配置
- 第五篇——Struts2的默认Action
- Python3学习之路~3.3 内置函数
- 【Darwin学习笔记】之获取系统处理器数量的方法
- springboot 1.5.x 使用tomcat8设置cookie的domain以dot开头报错