题意描述：有两个长度分别为p+1和q+1的序列，每个元素中的各个元素互不相同。都是1~n^2之间的整数，求A和B的最长公共子序列。（2<=n<=250，1<=p,q<=n^2）
分析：本题是LCS问题，但因为p和q可以高达250^2=62500，O(pq)的算法显然太慢。注意到A序列中所有元素互不相同，因此可以把A中的元素重新编号为1~p+1。这样新的A和B的LCS实际上就是B的LIS。可以在O(nlogn)时间内解决。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int maxn=251*251; 6 const int INF=1000000000; 7 int s[maxn],g[maxn],d[maxn]; 8 int num[maxn]; 9 10 int main() 11 { 12 int T; 13 scanf("%d",&T); 14 for(int kase=1;kase<=T;kase++) 15 { 16 int N,p,q,x; 17 scanf("%d %d %d",&N,&p,&q); 18 memset(num,0,sizeof(num)); 19 for(int i=1;i<=p+1;i++) {scanf("%d",&x);num[x]=i;} 20 int n=0; 21 for(int i=0;i<q+1;i++) {scanf("%d",&x);if(num[x]) s[n++]=num[x];} 22 for(int i=1;i<=n;i++) g[i]=INF; 23 int ans=0; 24 for(int i=0;i<n;i++) 25 { 26 int k=lower_bound(g+1,g+1+n,s[i])-g; 27 d[i]=k; 28 g[k]=s[i]; 29 ans=max(ans,d[i]); 30 } 31 printf("Case %d: %d ",kase,ans); 32 } 33 return 0; 34 }