首先,让我来看看LIS问题

Description

一个数的序列 bi,当 b1 < b2 < ... < bS 的时候,我们称这个序列是上升的。对于给定的一个序列(a1,a2,...,aN),我们可以得到一些上升的子序列(ai1,ai2,...,aiK),这里 1 ≤ i1 < i2 <...< iK ≤ N。比如,对于序列(1,7,3,5,9,4,8),有它的一些上升子序列,如(1,7),(3,4,8)等等。

这些子序列中最长的长度是 4,比如子序列(1,3,5,8)。

你的任务,就是对于给定的序列,求出最长上升子序列的长度。

Format

Input

输入的第一行是序列的长度 N(1 ≤ N ≤ 1000)。

第二行给出序列中的 N 个整数,这些整数的取值范围都在 0 到 10000。

Output

最长上升子序列的长度。

Samples

输入数据 1

7
1 7 3 5 9 4 8

Copy

输出数据 1

4

基础方法求解:

  • 当我们求1~n的LIS长度时,我们可以轻松的发现可以从以前的状态转移过来

  • 经典的动态规划问题!!
  • 于是我们开始设置状态
  • 我们设表示从以结尾的最长子序列长度
  • 注意初始化:
  • 时间复杂度是

Code:

#include<bits/stdc++.h>
using namespace std;
int n,a[10005],dp[10005],ans;
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++){
dp[i]=1;
for(int j=1;j<i;j++)
if(a[j]<a[i])
dp[i]=max(dp[i],dp[j]+1);
ans=max(dp[i],ans);
}
cout<<ans;
return 0;
}

优化

  • 甚至更大,复杂度的代码肯定会超时
  • 考虑优化?

  • 我们注意到,第二层枚举的时候,会枚举很多无用的状态
  • 比如:当我们枚举到 时,完全没有必要枚举,所以我们可以考虑优化
  • 我们使用贪心策略:当我们枚举的更小的时候,就更有可能和形成更长的子序列
  • 因此,我们可以单调维护前面所有可以考虑转移的数字!

二分(话说什么奇奇怪怪的优化都是他)

  • 新建一个数组, 表示最长上升子序列长度为的时候最大值
  • 我们保证数组存的是最大值的最小值
  • 比如有两个序列
  • ,
  • 最长子序列长度是3,但是存的是5(保证最小)
  • 如何维护这个数组呢?
  • 两种情况
  • >[当前最长LIS长度],我们就更新最长长度,把a[i]接到后面去
  • [当前最长LIS长度]时,我们就更新呗
  • 我们注意定义( 表示最长上升子序列长度为的时候的最小值)
  • 我们能做什么?
  • 不就是更新最小值吗?
  • 又因为数组是单调递增的(这个应该都知道吧)
  • 所以我们二分数组,找到第一个大于等于 的值,更新即可
  • 最后我们输出即可(如果觉得懵的话,可以自己举个例子看看)
  • 时间复杂度是:

Code:

#include<bits/stdc++.h>

using namespace std;
int n,m,a[100005],ans[100005],len;
int erfen(int sum){
int l=1,r=len,mid;
while(l<=r){
mid=(l+r)/2;
if(ans[mid]>=sum)
r=mid-1;
else
l=mid+1;
}
return l;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
len=1;
ans[1]=a[1];
for(int i=2;i<=n;i++){
if(a[i]>ans[len])
ans[++len]=a[i];
else{
int pos=erfen(a[i]);
ans[pos]=a[i];
}
}
cout<<len<<endl;
return 0;
}

考虑再次优化?

  • 当有些题目时间卡得非常紧的情况下,二分过大的常数可能导致超时,需要再次优化

  • 我们注意这条式子,发现我们第二层的任务是找前的LIS的最长长度

  • 这种修改需要进行单点修改,考虑使用树状数组进行优化

  • 表示以i结尾的最长上升子序列长度

  • 我们将原数组从小到大排序,并记录他原来的下标(有点像二分),设他为数组

  • 我们遍历到时,找到~的最大值,然后对这个值+1进行更新

  • 时间复杂度是:

  • 注意:如果不去重,就会成为最长不下降子序列

Code:

#include<bits/stdc++.h>
using namespace std;
struct node{int value,num;}a[30005];
int n,t[30005],b[30005],maxx;
bool cmp(node x,node y){
return x.value<y.value;
}
int lowbit(int x){
return x&(-x);
}
int ask(int x){//查找t1~tx的最大值
int res=-1e9;
for(;x;x-=lowbit(x))
res=max(res,t[x]);
return res;
}
void modify(int x,int r){//更新这个点的最大值
for(;x<=n;x+=lowbit(x))
t[x]=max(t[x],r);
}
void solve(){
for(int i=1;i<=n;i++){
int x=ask(a[i].num);
modify(a[i].num,++x);
maxx=max(maxx,x);
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)
cin>>b[i];
for(int i=1;i<=n;i++)
a[i].value=b[i],a[i].num=i;
sort(a+1,a+1+n,cmp);
solve();
cout<<maxx;
return 0;
}

(如果想了解树状数组,请到我的另一篇博客去咯loolook)

单看着干嘛?还不去写代码????!!!

最新文章

  1. Navigation Bar options for Android (based on photosomething project)
  2. 分分钟学会系列:mac地址泛洪攻击实验
  3. Dojo学习_组件属性
  4. 40页PPT勾画“互联网颠覆性思维”----诠释互联网思维
  5. The 3n + 1 problem 分类: POJ 2015-06-12 17:50 11人阅读 评论(0) 收藏
  6. Rolling Cursor Invalidations with DBMS_STATS.AUTO_INVALIDATE (文档 ID 557661.1)
  7. Java SE7新特性之try-with-resources语句
  8. 用 C# 做人脸检测(EmguCV)
  9. 递归-快速排序quickSort
  10. Linux下的文件查找类命令(转载)
  11. Python练习七
  12. cef3:禁止win10高dpi下cef对内部网页进行缩放
  13. ArrayList在foreach删除倒数第二个元素不抛并发修改异常的问题
  14. C# 多线程及同步简介示例
  15. python----操作文本文件
  16. HDU 2191 - 单调队列优化多重背包
  17. shell执行字符串中的命令
  18. Oracle安装部署之 oracle 11g install linux
  19. python写http post请求的四种请求体
  20. Eclipse的版本命名

热门文章

  1. 【一】ERNIE:飞桨开源开发套件,入门学习,看看行业顶尖持续学习语义理解框架,如何取得世界多个实战的SOTA效果?
  2. pta第二次博客
  3. Python基础部分:3、 pycharm的下载与使用
  4. jvm之垃圾收集二之常用垃圾收集器
  5. windows socket网络编程--事件选择模型
  6. mybatis中association和collection使用
  7. mindxdl--common--head_handler.go
  8. 链接脚本(Linker Scripts)语法和规则解析(自官方手册)
  9. 图扑 Web SCADA 零代码组态水泥生产工艺流程 HMI
  10. i春秋broken