LIS最长上升子序列
一般求解LIS有两种做法,第一种直接(n^2)暴力枚举,a数组记录原序列,设(f[i])表示枚举到第i位(即以第i个元素结尾)的最长上升子序列的长度;
for(int i=1;i<=n;i++)
f[i]=1;
//这个初始化应该挺好理解吧;
//初始看作每个元素自身构成一个序列,长度为1
for(int i=1;i<=n;i++){
for(int j=1;j<i;j++){
if(a[j]<a[i]&&f[i]<f[j]+1)
f[i]=f[j]+1;
}
ans=max(ans,f[i]);
}
ans即为最终答案.
这里主要是想介绍一下第二种(nlogn)的做法;设(f[i])表示长度为i的最长上升子序列的 末尾元素的最小值(这个设定好好理解一下),那么其实就是结合了贪心思想(很显然地,对于同样的长度为i的最长上升子序列,当前末尾元素越小的那个序列越有利于后面元素的加入);
for(int i=1;i<=n;i++){
f[i]=inf;
//把f[i]初始化为无穷大,是为了后面的比较大小
}
f[1]=a[1];
//初始长度为1的序列的末尾元素就是a[1]
int len=1;
//len记录最长上升子序列的长度
for(int i=2;i<=n;i++){
int l=0,r=len,mid;
if(a[i]>f[len])
f[++len]=a[i];
//如果枚举到的当前元素a[i]
//大于我们已经得到的最长上升子序列的末尾元素
//那么直接长度+1,更新f[len];
else{
//否则,不断在已经确定的最长上升子序列中
//查找一个能放下a[i]的合法位置
//因为我们之前确定的是最长上升子序列(单调序列)
//所以我们可以用二分查找
//(这个二分查找不懂的,可以自己手动模拟一下)
while(l<r){
mid=(l+r)/2;
if(f[mid]>a[i])r=mid;
else l=mid+1;
}
f[l]=min(a[i],f[l]);//更新最小末尾
}
}
len即是最终的答案
LCS最长公共子序列
和LIS一样,求解LCS一般也有两种做法,一种是(n^2)的暴力做法,设(f[i][j])表示第一个序列(序列a)当前枚举到第i个位置,第二个序列(序列b)当前枚举到第j个位置,所得到的最长公共子序列的长度;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
f[i][j]=max(f[i-1][j],f[i][j-1]);
if(a[i]==b[j])
f[i][j]=max(f[i][j],f[i-1][j-1]+1);
}
最后的答案就是f[n][m]
不得不说明一下,(n^2)做法是对于任意两个长度分别为n的a序列和m的b序列;
而以下(nlogn)的做法是对于两个序列长度都是n的且序列中的元素都是一样的(即a,b两个序列只是排列不一样);
看到这里,可能有大佬会问:对于两个没有限制条件的序列怎么求它们的最长公共子序列呢?本蒟蒻只好回答:不会
重点是第二种(nlogn)的做法,我们分析以下a,b两个序列的性质,它们的长度都是n并且序列内元素都是1~n,唯一的区别就是排列不同;
根据这些性质,我们可以设置一个pla数组来记录a序列中的元素在b序列中的位置,也不难看出(算了,先不给结论)
我们现在来看个简单的例子:
A: 3 2 4 1 5
B: 4 5 3 1 2
这样一个简单的例子,我们能够直接看出,最长公共子序列的长度为2(即由4和5构成的序列)(或者3和2构成的序列)(或者3和1)
那么按照上述方法设置一个pla数组来记录a序列中的元素在b序列中的位置,所以:
pla[3]=3;
pla[2]=5;
pla[4]=1;
pla[1]=4;
pla[5]=2;
我们来好好比较一下合法序列(4和5 或 3和2 或 3和1)在pla数组中的关系:
pla[4]=1; pla[5]=2;(1<2)
pla[3]=3; pla[2]=5;(3<5)
pla[3]=3; pla[1]=4;(3<4)
是不是看出了都是递增的关系,于是可以草率地得到这道题的结论,我们把a序列中的元素在b序列中的位置表示出来后(用pla数组记录),求解最长公共子序列相当于在pla数组中找一个最长上升子序列;
于是我们就成功地转化为了上述求LIS的问题(所以懒蒟蒻就不写注释了)
for(int i=1;i<=n;i++){
pla[a[i]]=i;
f[i]=inf;
}
int len=0;
for(int i=1;i<=n;i++){
int l=0,r=len,mid;
if(pla[b[i]]>f[len])
f[++len]=pla[b[i]];
else {
while(l<r){
mid=(l+r)/2;
if(f[mid]>pla[b[i]]) r=mid;
else l=mid+1;
}
f[l]=min(pla[b[i]],f[l]);
}
}
最后的答案就是len