UVa 10635 Prince and Princess

　　讲一下题目大意，就是有两个长度为p + 1和q + 1的序列，求它们的LCS。

　　如果用O（pq）的算法对于这道题来说还是太慢了。所以要另外想一些方法。注意到序列中的所有元素都不相同，所以两个序列中数对应的位置都是唯一的，就用第一个序列的元素对第二个序列的元素进行重新编号，记录它们在第一个序列中出现的位置(如果不存在就随便记一个不能达到的值)，不存在的话就说明它们对LCS没有贡献。那么看张图:

　　如果不能明白，那。。看张有关不合法情况的图:

　　有没有发现LCS的长度就是第二个序列的LIS的长度？

  1 /**
  2  * uva
  3  * Problem#10635
  4  * Accepted
  5  * Time:0ms
  6  */
  7 #include<iostream>
  8 #include<cstdio>
  9 #include<cctype>
 10 #include<cstring>
 11 #include<cstdlib>
 12 #include<cmath>
 13 #include<sstream>
 14 #include<algorithm>
 15 #include<map>
 16 #include<set>
 17 #include<queue>
 18 #include<vector>
 19 #include<stack>
 20 using namespace std;
 21 typedef bool boolean;
 22 #define INF 0xfffffff
 23 #define smin(a, b) a = min(a, b)
 24 #define smax(a, b) a = max(a, b)
 25 template<typename T>
 26 inline void readInteger(T& u){
 27     char x;
 28     int aFlag = 1;
 29     while(!isdigit((x = getchar())) && x != '-');
 30     if(x == '-'){
 31         x = getchar();
 32         aFlag = -1;
 33     }
 34     for(u = x - '0'; isdigit((x = getchar())); u = (u << 1) + (u << 3) + x - '0');
 35     ungetc(x, stdin);
 36     u *= aFlag;
 37 }
 38 
 39 template<typename T>
 40 class IndexedStack{
 41     public:
 42         T *p;
 43         int s;
 44         IndexedStack():s(0), p(NULL){    }
 45         IndexedStack(int size):s(0){
 46             p = new T[(const int)size];
 47         }
 48         boolean empty()        {    return s == 0;            }
 49         T top()            {    return p[s - 1];        }
 50         int size()        {    return s;            }
 51         void pop()        {    s--;                }
 52         void push(T& x)        {    p[s++] = x;            }
 53         void clear()        {    s = 0;                }
 54         T& operator [](int pos)    {    return p[pos];            }
 55 };
 56 
 57 int n, p, q;
 58 int *pce;
 59 int *pss;
 60 int *ets;
 61 
 62 inline void init(){
 63     readInteger(n);
 64     readInteger(p);
 65     readInteger(q);
 66     pce = new int[(const int)(p + 2)];
 67     pss = new int[(const int)(q + 2)];
 68     ets = new int[(const int)(n * n + 1)];
 69     memset(ets, 0, sizeof(int) * (n * n + 1)); 
 70     p += 1, q += 1;
 71     for(int i = 1; i <= p; i++){
 72         readInteger(pce[i]);
 73         ets[pce[i]] = i;
 74     }
 75     for(int i = 1; i <= q; i++){
 76         readInteger(pss[i]);
 77         pss[i] = ets[pss[i]];
 78     }
 79     delete[] ets;
 80 }
 81 
 82 int upper_bound(int *a, int from, int end, int val){
 83     int l = from, r = end - 1;
 84     while(l <= r){
 85         int mid = (l + r) >> 1;
 86         if(val < a[mid])    r = mid - 1;
 87         else l = mid + 1;
 88     }
 89     return r + 1;
 90 }
 91 
 92 IndexedStack<int> s;
 93 inline int lis(){
 94     s = IndexedStack<int>(q + 1);
 95     for(int i = 1; i <= q; i++){
 96         if(pss[i] == 0)    continue;
 97         int l = upper_bound(s.p, 0, s.size(), pss[i]);
 98         if(l == s.size()) s.push(pss[i]);
 99         else s[l] = pss[i];
100     }
101     return s.size();
102 }
103 
104 int T, kase;
105 inline void solve(){
106     int len = lis();
107     printf("Case %d: %d
", kase, len);
108     delete[] pss;
109     delete[] pce;
110 }
111 
112 int main(){
113     readInteger(T);
114     while(T--){
115         kase++;
116         init();
117         solve();
118     }
119     return 0;
120 }