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

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

题目链接-P1439 【模板】最长公共子序列

解题思路
$LCS(最长公共子序列)———>LIS(最长上升子序列)$

• 首先根据概念，最长公共子序列，就是两段所含数字完全一样且顺序也一样的序列
• 我们可以将序列离散化，使$pos[a_i]=i$，比如： $A=${$3,2,1,4,5$} $B=${$1,2,3,4,5$}，我们可以给$A$编号为: a b c d e，那么$B$: c b a d e，$pos[]=${$3,2,1,4,5$}，按照$pos$数组映射后$B'=${$3,2,1,4,5$}
• 这样我们就把问题转换成了求$pos[]$和$B'[]$的最长上升子序列，因为数据范围比较大，朴素法$On^2$肯定会超时，我们可以用二分法求最长上升子序列
• 其实运用了贪心的思想：$low[i]$是上升子序列长度为$i$的上升子序列的最小末尾数值，显然递增子序列末尾元素越小，后面的元素就越容易加入该上升子序列中
• 即每遇到一个新的元素时，就跟已经记录的$low$数组当前所记录的最长升子序列的末尾元素相比较，如果大于此元素，就填到末尾元素的下一个，否则就不断向前找，直到找到一个刚好比它大的元素并替换
• 具体操作见代码

附上代码

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
#define int long long
#define lowbit(x) (x &(-x))
#define endl '\n'
using namespace std;
const int INF=0x3f3f3f3f;
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const double PI=acos(-1.0);
const double e=exp(1.0);
const double eps=1e-10;
const int M=1e9+7;
const int N=2e5+10;
typedef long long ll;
typedef pair<int,int> PII;
typedef unsigned long long ull;
int b[N],low[N],pos[N];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);

	int n,tmp,l=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>tmp;
		pos[tmp]=i;
	}
	for(int i=1;i<=n;i++){
		cin>>tmp;
		b[i]=pos[tmp];
		if(b[i]>low[l])//如果第i个数大于low数组的最大的数
			low[++l]=b[i];//直接接在low数组的后面
		else//如果第i个数不大于low数组中最大的数
			low[lower_bound(low+1,low+1+l,b[i])-low]=b[i];
			//那么就二分查找low中第一个小于等于b[i]的元素的位置，替换
	}
	cout<<l<<endl;
	return 0;
}

本文地址：https://blog.csdn.net/Fiveneves/article/details/107241706