LCS 问题
LCS，即最长公共子序列。
1. 朴素的求法
使用动态规划，\(dp_{i,j}\) 代表以序列 \(a\) 第 \(i\) 个字母结尾，序列 \(b\) 第 \(j\) 个字母结尾的 LCS 长度。得动态转移方程：
\[dp_{i,j} = \left\{\begin{matrix} \max(dp_{i-1,j},dp_{i,j-1}) & a_i \ne b_j\\ dp_{i-1,j-1} & a_i = b_j \end{matrix}\right. \]Code1
#include <iostream>
using namespace std;
#define MAXN 10005
int f[MAXN][MAXN];
int a[MAXN],b[MAXN];
int main()
{
int n;
cin>>n;
int m=n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=m;i++) cin>>b[i];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(a[i]==b[j]) f[i][j]=f[i-1][j-1]+1;
else f[i][j]=max(f[i][j-1],f[i-1][j]);
}
}
cout<<f[n][m];
return 0;
}
时间复杂度：\(O(n^2)\)。
2. 优化处理
考虑使用 LIS 解决 LCS。
因为两个序列都是 \(1 \sim n\) 的全排列，那么两个序列元素互异且相同，也就是说只是位置不同罢了，那么我们通过一个 \(map\) 数组将 \(a\) 序列的数字在 \(b\) 序列中的位置表示出来。
因为最长公共子序列是按位向后比对的，所以 \(a\) 序列每个元素在 \(b\) 序列中的位置如果递增，就说明 \(b\) 中的这个数在 \(a\) 中的这个数整体位置偏后，可以考虑纳入 LCS，那么就可以转变成时间复杂度为 \(O(n \log n)\) 的求用来记录新的位置的 \(map\) 数组中的 LIS！（代码展示的仅是洛谷 P1439 的代码，有一定局限性【仅为 \(a,b\) 中没有重复项时】）
Code2
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>
using namespace std;
#define MAXN 100005
int a[MAXN],b[MAXN],c[MAXN];
unordered_map<int,int> mp;
vector<int> vec;
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n;i++) cin>>b[i];
for(int i=0;i<n;i++) mp[a[i]]=i;
for(int i=0;i<n;i++) c[i]=mp[b[i]];
for(int i=0;i<n;i++)
{
int tem=lower_bound(vec.begin(),vec.end(),c[i])-vec.begin();
if(tem==vec.size())
vec.push_back(c[i]);
else vec[tem]=c[i];
}
cout<<vec.size();
return 0;
}