標題效果：有兩個長度p+1和q+1該序列。的各種元素的每個序列不是相互同。并1~n^2之間的整數。個序列的第一個元素均為1。

求出A和B的最長公共子序列長度。

分析：本題是LCS問題，可是p*q<=62500,O(pq)的算法顯然會LE。在這里有一個條件，每一個序列中的各個元素互不同樣，所以能夠把A中元素又一次編號為1~p+1。比如，例子中A={1,7,5,4,8,3,9}，B={1,4,3,5,6,2,8,9}。因此把A又一次編號為{1,2,3,4,5,6,7}。則B就是{1,4,6,3,0,0,5,7}（在A中沒有出現過的元素一定不會是公共子序列中的元素），當中0表示A中沒有出現過，能夠直接刪去。這時B={1,4,6,3,5,7}，元素的值代表著B中和原A中元素值同樣的。在A中的位置。子序列的位置一定要是單調遞增的,這樣求得的最長子序列才相當于原Ａ和Ｂ的最長公共子序列。由此。成功轉化成LIS問題`(*∩_∩*)′。

求出B的LIS就可以。時間復雜度就能夠優化到O(nlogn)了。

以下貼上代碼(借鑒lrj巨犇的=-=)

#include<iostream> #include<cstring> #include<algorithm> using namespace std;const int maxn = 250*250; const int INF = 1e9; int s[maxn],g[maxn],d[maxn]; int num[maxn]; //num[x]為整數x的新編號。num[x]=0表示x沒有在A中出現過int main() {int T;cin>>T;for(int kase=1;kase<=T;kase++){int N,p,q,x;cin>>N>>p>>q;memset(num,0,sizeof(num));for(int i=1;i<=p+1;i++){cin>>x;num[x]=i;}int n=0;for(int i=0;i<q+1;i++){cin>>x;if(num[x]) s[n++]=num[x];}//求解s[0]...s[n-1]的LISfor(int i=1;i<=n;i++) g[i]=INF;int ans=0;for(int i=0;i<n;i++){int k=lower_bound(g+1,g+n+1,s[i])-g;d[i]=k;g[k]=s[i];ans=max(ans,d[i]);}cout<<"Case "<<kase<<": "<<ans<<endl;}return 0; }
關于lower_bound函數（二分查找函數），是STL庫的。不懂的童鞋請看http://blog.csdn.net/u012198382/article/details/24887181（lower_bound說明）

版權聲明：本文博客原創文章。博客，未經同意，不得轉載。

轉載于:https://www.cnblogs.com/blfshiye/p/4728927.html

總結

以上是生活随笔為你收集整理的uva 10635 Prince and Princess（LCS成问题LIS问题O(nlogn)）的全部內容，希望文章能夠幫你解決所遇到的問題。

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