P1439 【模板】最长公共子序列

P1439 【模板】最长公共子序列

实际上这题不能算 dp，应该是贪心。

先区分两个概念：

• LIS：Longest Increasing Subsequence，最长递增子序列
• LCS：Longest Common Subsequence，最长公共子序列

将 b 数组中的元素映射为其在 a 数组中的位置，问题就从 LCS 变成了 LIS。

在求解 LIS 时，开一个单调栈，如果 a[i] 大于等于栈顶，直接进栈。否则二分栈内所有元素，将第一个大于它的元素改为它，最终答案就是栈的大小。

原理/正确性：贪心选择它能换掉的最大元素，栈内元素越小，后面元素进栈的门槛也就越低，就能实现最大化栈内元素。

注意：此算法只能实现求个数，无法求出每一个是什么，如果有这个需求，只能用 \(O(n^2)\) dp。

代码：

#include<bits/stdc++.h>
using namespace std;
int n;
int a[100010],b[100010];
int mp[100010];
int c[100010];
int stk[100010],tot;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		mp[a[i]]=i;
	}
	for(int i=1;i<=n;i++){
		cin>>b[i];
	}
	for(int i=1;i<=n;i++){
		c[i]=mp[b[i]];
	}
	for(int i=1;i<=n;i++){
		if(c[i]>stk[tot]){
			stk[++tot]=c[i];
		}
		else{
			*lower_bound(stk+1,stk+tot+1,c[i])=c[i];
		}
	}
	cout<<tot<<endl;
}