UVA 10635 - Prince and Princess LCS转化为LIS

题目大意：

有两串长度分别为p+1和q+1的序列，每个序列中的各个元素互不相同，且都是1~n*n之间的整数，两个序列的第一个元素是1，求A和B的最长公共子序列长度。

思路:

求LCS的经典解法时间复杂度为O(P*Q)，而p和q可能为250*250=62500.

因为A序列中的所有元素均不相同，所以可以把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}（0表示在A中没出现过，可以直接删掉，因为LCS肯定没有）这样新的A和B的LCS其实就是新的B的LIS，LIS可以在O(nlongn)解决。

#include
  
   
#include
   
     #include
    
      using namespace std; const int MAXN=250*250+10; const int INF=9999999; int b[MAXN],n,p,q; int g[MAXN],id[MAXN],x[MAXN];//g[i]:ICS为i时候的最小下标，x[i]：lis值 int main() { int T,kase=1; scanf(%d,&T); while(T--) { int temp,len=0; scanf(%d%d%d,&n,&p,&q); memset(id,0,sizeof(id)); for(int i=1;i<=p+1;i++) { scanf(%d,&temp); id[temp]=i; } for(int i=0;i