uva10635 LCS映射转LIS

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <stdlib.h>
 4 #include <algorithm>
 5 #include <iostream>
 6 #include <queue>
 7 #include <stack>
 8 #include <vector>
 9 #include <map>
10 #include <set>
11 #include <string>
12 using namespace std;
13 typedef long long LL;
14 const int INF = 1<<30;
15 const int N = 90000;
16 int a[N],b[N];
17 int reflect[N];
18 int st[N],top;
19 int main()
20 {
21     int t,n,p,q,i,j,tCase;
22     scanf("%d",&tCase);
23     for(t=1; t<=tCase; ++t)
24     {
25         top = 0;
26         scanf("%d%d%d",&n,&p,&q);
27         p++;
28         q++;
29         for(i=1; i<=p; ++i)
30         {
31             scanf("%d",&a[i]);
32             reflect[a[i]] = i;
33         }    
34         for(i=1; i<=q; ++i)
35         {
36             scanf("%d",&b[i]);
37             b[i] = reflect[b[i]];
38         }    
39         st[top] = b[1];
40         for(i=2; i<=q; ++i)
41         {
42             if(b[i] > st[top])
43             {
44                 st[++top] = b[i];
45             }
46             else
47             {
48                 int low = 0, high = top;
49                 while(low <= high)
50                 {
51                     int mid = (low + high) >> 1;
52                     if(b[i] > st[mid])
53                         low = mid + 1;
54                     else
55                         high = mid - 1;
56                 }
57                 st[low] = b[i];
58             }    
59         }
60         printf("Case %d: %d\n",t,top+1);
61     }
62     
63     return 0;
64 }