最长公共子序列问题【LCS】

题目简义

对于给定的序列$A$和$B$
要求求出最长序列$M$使得$M \subseteq A$且$M \subseteq B$

通解(无特殊性质)

来源
该算法时间复杂度为$O(n^{2})$
我们用$f(i, j)$表示$A$序列只考虑前$i$个元素$B$序列只考虑前$j$个元素的最长长度
那么我们进行分类讨论$f(i, j)$的情况

1. $A_{i}$与$B_{j}$若不匹配，则有$f(i, j) = max(f(i,j - 1),f(i - 1, j))$
2. $A_{i}$与$B_{j}$相匹配，则有$f(i, j) = f(i - 1, j -1 ) + 1$

以此枚举$i$和$j$即可

for(int i = 1; i <= n; i ++){
	for(int j = 1; j <= n; j ++){
		f[i][j] = max(f[i - 1][j], f[i][j - 1]);
		if(a[i] == b[i])f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
	}
}

事实上，LCS问题还有一种变式

来源
对于原问题我们增加一个条件：A序列不存在重复元素
通常要求在1e5的范围内求解，若用第一种方法，很显然会TLE或MLE
我们更换思路，引入序列$B'_{i}$表示$B_{i}$在$A_{i}$中的问题
则对于原序列$M$在$B'$中对应的数呈上升关系，即可将LIS问题转化为LCS问题
然后使用LCS的二分优化$O(nlogn)$时间复杂度下求解

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 1e6 + 10;

int q[N], id[N];

int main(){
	memset(id, -1, sizeof id);
	
	int n;
	scanf("%d", &n);
	
	for(int i = 1; i <= n; i ++){
		int x;
		scanf("%d", &x);
		id[x] = i;
	}
	
	int tt = 0;
	q[0] = -1;
	for(int i = 1; i <= n; i ++){
		int x;
		scanf("%d", &x);
		
		if(id[x] == -1)continue;
		int k = id[x];
		
		int l = 0, r = tt;
		while (l < r){
			int mid = l + r + 1 >> 1;
			if(k > q[mid])l = mid;
			else r = mid - 1;
		}
		
		q[r + 1] = k;
		tt = max(r + 1, tt);
	}
	
	printf("%d", tt);
	
	return 0;
	
}