题目链接：
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1576
题意：给出两个长度分别为p+1，q+1的数字序列，序列中数字范围为1~n*n，序列中数字不重复，让求序列的最大公共子序列。
解析：这里要用到O（n*log(n））的LIS最长上升子序列来求，具体步骤如下：
①.设有序列A，B，记序列A中各个元素在B 中的位置(记录时降序排列)；
②.将A中的“每个元素”替换为“该元素在B 中的位置集合(记录时降序排列)”；
③.然后求变化后的A的最长递增子序列。
例如：有A={a,b,a,c,x}，B={b,a,a,b,c,a}则有a={6,3,2},b={4,1},c={5};x=/;（注意降序排列）
然后按A中次序排出{a(6,3,2),b(4,1),a(6,3,2),c(5),x()}={6,3,2,4,1,6,3,2,5}；对此序列求最长递增子序列即可。
将求出来的最长上升子序列每个元素作为下标，对应到变化前的A中的可得到一个序列，即A与B的最长公共子序列。
其正确性的必要条件：
①.由于变化后的A集合与变化后前A集合元素是一一对应的，所以可以保证选出的最长上升子序列对于变化前A中的元素是遵循排列顺序的。
②.由于选出的元素的本质是B中某元素的下标，由于所选序列上升的，所以可以保证选出的最长上升子序列对于B的元素是遵循排列顺序的。
③.选出的元素一定即在A中又在B中，即是A与B的公共元素
④.LIS与LCS中两个最长相对应，保证结果是最长的。
注：这里求A中元素在B 中的位置集合时要降序排列能使得同一元素只选一次
以上是网上看到的LIS转LCS解释但是没有看到具体的代码。。。
下面的代码是另一种方式：
设A={a1,a2,a3...ap,ap+1}，将每个元素ai用mark[ai]记录其下标i；
设B={b1,b2,b3...bq,bq+1},生成数组ans[1]~ans[q+1]，其中ans[i]=mark[b[i]]
然后求ans数组的的最长递增子序列就行了
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M = 250*250+10;int ans,n,p,q;
int a[M],b[M];
int mark[M],dp[M];
int main()
{int T,cas=0;scanf("%d",&T);while(T--){memset(mark,0,sizeof(mark));scanf("%d%d%d",&n,&p,&q);for(int i=1;i<=p+1;i++){scanf("%d",&a[i]);mark[a[i]]=i;}for(int i=1;i<=q+1;i++){scanf("%d",&n);b[i]=mark[n];dp[i]=0;}int cnt=0;ans=1;for(int i=1;i<=q+1;i++){int k=lower_bound(dp,dp+cnt,b[i])-dp;dp[k]=b[i];if(k==cnt) cnt++;ans=max(cnt,ans);}printf("Case %d: %d\n",++cas,ans);}return 0;
}参考：
LIS原理：https://blog.csdn.net/accelerator_/article/details/11339459
http://blog.51cto.com/karsbin/966387
https://blog.csdn.net/tengfei461807914/article/details/51031355