首页 > 代码库 > [洛谷P1439]排列LCS问题
[洛谷P1439]排列LCS问题
题目大意：给你两个1~n的排列，求他们的LCS。
解题思路：由于是1~n的排列，每个数会且只会出现1次。我们可以把一个序列映射成1，2，3，4……然后将另一个序列按照这个映射进行改变。由于前一个序列已经有序，那么后一个序列的最长上升子序列（LIS）肯定是前一个的子序列，由于LIS最长，所以它的值也是LCS的值。故我们只要这样做一遍LIS即可。用单调队列优化后的LIS，时间复杂度$O(n\log n)$。
C++ Code：
#include<cstdio>#include<algorithm>#include<cstring>using namespace std;int n,a[100005],b[100005],p[100005];int main(){ scanf("%d",&n); for(int i=1;i<=n;++i){ scanf("%d",&a[i]); p[a[i]]=i; } for(int i=1;i<=n;++i){ int x; scanf("%d",&x); b[i]=p[x]; } memset(p,0,sizeof p); p[0]=-1; int k=0; for(int i=1;i<=n;++i){ if(b[i]>p[k])p[++k]=b[i]; int q=lower_bound(p,p+k,b[i])-p; if(b[i]<p[q])p[q]=b[i]; } printf("%d\n",k); return 0;}
[洛谷P1439]排列LCS问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。