最长公共子序列
给定两个长度分别为 \(n,m\) 的序列
试求出最长的公共子序列。
\(\mathcal O(n^2)\) 做法
我们考虑进行动态规划
设 \(f[i][j]\) 表示看完 \(a\) 数组的前 \(i\) 位，\(b\) 数组的前 \(j\) 位的最长公共子序列的长度
那么我们最终的答案就是 \(f[n][m]\)
考虑如何转移，我们分情况来讨论。
当 \(a[i]=b[j]\) 时
\[f[i][j]=f[i-1][j-1]+1 \]否则
\[f[i][j]=f[i-1][j-1] \]同时我们考虑继承前面的答案，即
\[f[i][j]=\mathrm max\{ f[i-1][j],f[i][j-1],f[i][j]\} \]不难发现 \(f[i-1][j-1]\) 一定不会比 \(f[i-1][j]\) 和 \(f[i][j-1]\) 更优，所以我们可以这样来写：
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)
}
}
还是挺好理解的qwq
但是，我们怎么得到 \(LCS\) 本身而非 \(LCS\) 的长度呢？
也是用一个二维数组 \(b\) 来表示：
在对应字符相等的时候，用↖标记
在 \(p1 >= p2\) 的时候，用↑标记
在 \(p1 < p2\) 的时候，用←标记
伪代码：
若想得到 \(LCS\)，则再遍历一次 \(b\) 数组就好了，从最后一个位置开始往前遍历：
如果箭头是↖，则代表这个字符是 \(LCS\) 的一员，存下来后 i--,j--
如果箭头是←，则代表这个字符不是 \(LCS\) 的一员，j--
如果箭头是↑ ，也代表这个字符不是 \(LCS\)的一员，i--
如此直到 \(i = 0\) 或者 \(j = 0\) 时停止，最后存下来的字符就是所有的 \(LCS\) 字符
\(\mathcal O(nlogn)\) 做法
最长上升子序列 \((LIS)\)是可以用来优化最长公共子序列的。
我们通过一个 \(map\) 映射将 \(A\) 序列的数字在 \(B\) 序列中的位置表示出来(如果没有就为0)
因为最长公共子序列是按位向后比对的，所以 \(A\) 序列每个元素在 \(B\) 序列中的位置如果递增，就说明 \(B\) 中的这个数在 \(A\) 中的这个数整体位置偏后，可以考虑纳入 \(LCS\) ——那么就可以转变成求用来记录新的位置的数组中的 \(LIS\)。
\(LIS\) 的 \(\mathcal O(nlogn)\) 算法
#include<bits/stdc++.h>
using namespace std;
const int N=300010;
int a[N],b[N],n,m,ans;
unordered_map<int,int> mp;//映射关系
int dp[N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) scanf("%d",&a[i]),mp[a[i]]=i;
for(int i=1;i<=m;i++) scanf("%d",&b[i]),b[i]=mp[b[i]];
memset(dp,0x3f,sizeof(dp));
dp[1]=b[1];
ans=1;
for(int i=2;i<=m;i++){
if(b[i]>dp[ans]) {dp[++ans]=b[i];continue;}
int l=1,r=ans,res=0;
while(l<=r){
int mid=(l+r)>>1;
if(dp[mid]<b[i]){
res=mid;
l=mid+1;
}else{
r=mid-1;
}
}
dp[res+1]=min(dp[res+1],b[i]);
}
cout<<ans;
return 0;
}