[题解]UVa 10635 Prince and Princess

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

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

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

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

 /**

  * uva

  * Problem#10635

  * Accepted

  * Time:0ms

  */

 #include<iostream>

 #include<cstdio>

 #include<cctype>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<sstream>

 #include<algorithm>

 #include<map>

 #include<set>

 #include<queue>

 #include<vector>

 #include<stack>

 using namespace std;

 typedef bool boolean;

 #define INF 0xfffffff

 #define smin(a, b) a = min(a, b)

 #define smax(a, b) a = max(a, b)

 template<typename T>

 inline void readInteger(T& u){

     char x;

     int aFlag = ;

     while(!isdigit((x = getchar())) && x != '-');

     if(x == '-'){

         x = getchar();

         aFlag = -;

     }

     for(u = x - ''; isdigit((x = getchar())); u = (u << ) + (u << ) + x - '');

     ungetc(x, stdin);

     u *= aFlag;

 }

 template<typename T>

 class IndexedStack{

     public:

         T *p;

         int s;

         IndexedStack():s(), p(NULL){    }

         IndexedStack(int size):s(){

             p = new T[(const int)size];

         }

         boolean empty()        {    return s == ;            }

         T top()            {    return p[s - ];        }

         int size()        {    return s;            }

         void pop()        {    s--;                }

         void push(T& x)        {    p[s++] = x;            }

         void clear()        {    s = ;                }

         T& operator [](int pos)    {    return p[pos];            }

 };

 int n, p, q;

 int *pce;

 int *pss;

 int *ets;

 inline void init(){

     readInteger(n);

     readInteger(p);

     readInteger(q);

     pce = new int[(const int)(p + )];

     pss = new int[(const int)(q + )];

     ets = new int[(const int)(n * n + )];

     memset(ets, , sizeof(int) * (n * n + ));

     p += , q += ;

     for(int i = ; i <= p; i++){

         readInteger(pce[i]);

         ets[pce[i]] = i;

     }

     for(int i = ; i <= q; i++){

         readInteger(pss[i]);

         pss[i] = ets[pss[i]];

     }

     delete[] ets;

 }

 int upper_bound(int *a, int from, int end, int val){

     int l = from, r = end - ;

     while(l <= r){

         int mid = (l + r) >> ;

         if(val < a[mid])    r = mid - ;

         else l = mid + ;

     }

     return r + ;

 }

 IndexedStack<int> s;

 inline int lis(){

     s = IndexedStack<int>(q + );

     for(int i = ; i <= q; i++){

         if(pss[i] == )    continue;

         int l = upper_bound(s.p, , s.size(), pss[i]);

         if(l == s.size()) s.push(pss[i]);

         else s[l] = pss[i];

     }

     return s.size();

 }

 int T, kase;

 inline void solve(){

     int len = lis();

     printf("Case %d: %d\n", kase, len);

     delete[] pss;

     delete[] pce;

 }

 int main(){

     readInteger(T);

     while(T--){

         kase++;

         init();

         solve();

     }

     return ;

 }

巴特西

[题解]UVa 10635 Prince and Princess

最新文章

热门文章