題目大意：給你兩個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; }

?

轉載于:https://www.cnblogs.com/Mrsrz/p/7291268.html

總結

以上是生活随笔為你收集整理的[洛谷P1439]排列LCS问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。