P1439 最长公共子序列（二分求最长公共子序列）

题目：??https://www.luogu.com.cn/problem/P1439

思想：

首先，我们可以想到，最长公共子序列，就是两段所含数字完全一样，并且数字的顺序也是完全一样的序列。

而顺序，我们可以想到类似哈希的思想，考虑建立一个类似map的关系数组f[ai]=i，那么我们找到的序列只要是上升的，顺序就是一样的，然后考虑数字完全一样，由于我们已经有了一个f[ai]=i,所以我们把对应的bi改成f[bi]，就可以确保数字相等了呀！

这时，就是在f[bi]的数组中求个最长上升子序列了，二分搞一搞就好了。STL大法好！

代码：

?

// Problem: C - 最长公共子序列
// Contest: Virtual Judge - CQJTU-DP题单1——线性DP
// URL: https://vjudge.net/contest/574209#problem/C
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 2e5+5;
const int inf = 0x3f3f3f3f;

int n;
int a[N],b[N];
int f[N];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin>>n;
	map<int,int> mp;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		mp[a[i]]=i;
	}
	for(int i=1;i<=n;i++){
		cin>>b[i];
		//cout<<mp[b[i]]<<' ';
	}
	//cout<<"\n";
	//mp[b[i]]可以表示a数组中的每个数在b中的位置保证数字一样
	//然后找最长上升子序列保证顺序一样
	memset(f,127,sizeof(f));
	f[0]=0;
	int cnt=0;
	for(int i=1;i<=n;i++){
		if(mp[b[i]]>f[cnt]){  //找到b数组的最长上升子序列
			f[++cnt]=mp[b[i]];
		}
		else{
			int l=0,r=cnt;
			while(l<r){
				int mid=(l+r)/2;
				if(f[mid]>mp[b[i]]){
					r=mid;
				}
				else l=mid+1;
			}
			f[l]=min(mp[b[i]],f[l]);
		}
		/*
		for(int i=1;i<=cnt;i++){
			cout<<mp[i]<<' ';
		}
		cout<<"\n";
		*/
	}
	cout<<cnt<<"\n";
	
	
	
	return 0;	

}