See LCS again

时间限制：1000 ms | 内存限制：65535 KB

难度：3

描述

There are A, B two sequences, the number of elements in the sequence is n、m;

Each element in the sequence are different and less than 100000.

Calculate the length of the longest common subsequence of A and B.

 

输入

The input has multicases.Each test case consists of three lines;

The first line consist two integers n, m (1 < = n, m < = 100000);

The second line with n integers, expressed sequence A;

The third line with m integers, expressed sequence B;

 

输出

For each set of test cases, output the length of the longest common subsequence of A and B, in a single line.

样例输入

5 4

1 2 6 5 4

1 3 5 4

样例输出

3

上传者

TC_胡仁东

 

解题：一种LCS转LCS的nlogn的算法。是严格上升的LCS。

 

首先是LCS，我们把a序列中的每个元素在b中出现的位置保存起来，再按照降序排列，排列后再代入a的每个对应元素，那就转化为了求这个新的序列的最长上升子序列了。如：a[] = {a, b, c,} b[] = {a,b,c,b,a,d},那么a中的a，b，c在b中出现的位置分别就是{0,4},{1,3},{2}。分别按降序排列后代入a序列就是{4,0,2,3,1},之所以要按照降序排列，目的就是为了让每个元素只取到一次。

接下来的问题就是要求最长升序子序列问题了，也就是求LIS。

 特殊情况下，会退化得很严重。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              
               10 #include 
               
                11 #include 
                
                 12 #include 
                 
                  13 #define LL long long14 #define pii pair
                  
                   15 #define INF 0x3f3f3f3f16 using namespace std;17 struct info{18 int num,pos;19 };20 int n,m,tot,sa[100010],sc[200010],q[200010],head,tail;21 info sb[100010];22 bool cmp(const info &x,const info &y){23 return x.num < y.num;24 }25 int bsearch(int lt,int rt,int val){26 int mid,pos = -1;27 while(lt <= rt){28 int mid = (lt+rt)>>1;29 if(val <= sb[mid].num){30 pos = mid;31 rt = mid-1;32 }else lt = mid+1;33 }34 return pos;35 }36 int binsearch(int lt,int rt,int val){37 while(lt <= rt){38 int mid = (lt+rt)>>1;39 if(q[mid] < val) lt = mid+1;40 else rt = mid-1;41 }42 return lt;43 }44 int main() {45 while(~scanf("%d %d",&n,&m)){46 head = tail = tot = 0;47 for(int i = 1; i <= n; i++) scanf("%d",sa+i);48 for(int i = 1; i <= m; i++){49 scanf("%d",&sb[i].num);50 sb[i].pos = i;51 }52 sort(sb+1,sb+m+1,cmp);53 for(int i = 1; i <= n; i++){54 int tmp = bsearch(1,m,sa[i]);55 while(tmp > 0 && sb[tmp].num == sa[i]) sc[tot++] = sb[tmp++].pos;56 }57 for(int i = 0; i < tot; i++){58 if(head == tail || q[head-1] < sc[i]){59 q[head++] = sc[i];60 }else{61 int tmp = binsearch(tail,head-1,sc[i]);62 q[tmp] = sc[i];63 }64 }65 printf("%d\n",head-tail);66 }67 return 0;68 }