标题效果：有两个长度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]的LIS
for(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说明）
版权声明：本文博客原创文章。博客，未经同意，不得转载。