c/c++语言开发共享洛谷P1439 【模板】最长公共子序列

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

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

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

• 首先根据概念，最长公共子序列，就是两段所含数字完全一样且顺序也一样的序列
• 我们可以将序列离散化，使$pos[a_i]=i$pos[ai​]=i，比如： $A=$A={$3,2,1,4,5$3,2,1,4,5} $B=$B={$1,2,3,4,5$1,2,3,4,5}，我们可以给$A$A编号为: a b c d e，那么$B$B: c b a d e，$pos[]=$pos[]={$3,2,1,4,5$3,2,1,4,5}，按照$pos$pos数组映射后$B’=$B′={$3,2,1,4,5$3,2,1,4,5}
• 这样我们就把问题转换成了求$pos[]$pos[]和$B'[]$B′[]的最长上升子序列，因为数据范围比较大，朴素法$On^2$On2肯定会超时，我们可以用二分法求最长上升子序列
• 其实运用了贪心的思想：$low[i]$low[i]是上升子序列长度为$i$i的上升子序列的最小末尾数值，显然递增子序列末尾元素越小，后面的元素就越容易加入该上升子序列中
• 即每遇到一个新的元素时，就跟已经记录的$low$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; } 

c/c++开发分享洛谷P1439 【模板】最长公共子序列地址：https://blog.csdn.net/Fiveneves/article/details/107241706