題目大意：有兩個長度分別為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
#include
#include
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>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
關於lower_bound函數（二分查找函數），是STL庫的，不懂的童鞋請看http://blog.csdn.net/u012198382/article/details/24887181（lower_bound用法）
