关于LIS和LCS

本文主要用于记录$LIS$和$LCS$的一些思想

$LIS$,即最长上升子序列问题

$LCS$,即最长公共子序列问题

两种类型相似的典型动态规划问题,这里只讲$O$$($$n$$logn$$)$算法

$LIS$

首先设$f$$[$$i$$]$为长度为$i$的上升子序列最后一位的值

好像听起来感觉稍微有点绕哈

因为$f$$[$$i$$]$也是一个单调上升序列

所以我们每次插入一个新的数字,就可以二分查找出一个数字

使得每次替换最优,这里运用了贪心的思想

1
2
3
4
5
6
7
8
9
10
11
12
#include<bits/stdc++.h>
using namespace std;
int n,ans,a[100001],f[100001];
const int INF=2000000002;
int main() {
n=read();
for(register int i=0;i<n;++i) scanf("%d",&a[i]);
for(register int i=0;i<n;++i) f[i]=INF;
for(register int i=0;i<n;++i) *lower_bound(f,f+n,a[i])=a[i];
printf("%d\n",lower_bound(f,f+n,INF)-f);
return 0;
}

$LCS$

解决这个问题的本质是把该问题转化为$LIS$

当两个序列中元素全部相同的情况下

我们可以用$cap$$[$$i$$]$来记录$i$元素在序列$a$中的位置

然后对序列$b$进行类似$LIS$的操作即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
const int maxn=100001;
int n,l,r,ans,mid,a[maxn],b[maxn],f[maxn],cap[maxn];
int main() {
scanf("%d",&n);
for(register int i=1;i<=n;++i) scanf("%d",&a[i]),cap[a[i]]=i;
for(register int i=1;i<=n;++i) scanf("%d",&b[i]),f[i]=mod;
for(register int i=1;i<=n;++i) {
l=0,r=ans;
if(cap[b[i]]>f[ans]) f[++ans]=cap[b[i]];
else {
l=lower_bound(f,f+r+1,cap[b[i]])-f;
f[l]=min(f[l],cap[b[i]]);
}
}
printf("%d\n",ans);
return 0;
}