UVa 10635 (LIS+二分) Prince and Princess

题目的本意是求LCS，但由于每个序列的元素各不相同，所以将A序列重新编号{1,2,,,p+1}，将B序列重新编号，分别为B中的元素在A中对应出现的位置(没有的话就是0)。

在样例中就是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在求LIS时可以忽略)

这样求A、B的LCS就转变为求B的LIS

求LIS用二分优化，时间复杂度为O(nlogn)

第一次做的用二分求LIS的题是HDU 1025

http://www.cnblogs.com/AOQNRMGYXLMV/p/3862139.html

在这里再复习一遍

 //#define LOCAL

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int maxn =  * ;

 int num[maxn], s[maxn], dp[maxn];

 int main(void)

 {

     #ifdef LOCAL

         freopen("10635in.txt", "r", stdin);

     #endif

     int T, kase;

     scanf("%d", &T);

     for(kase = ; kase <= T; ++kase)

     {

         int N, p, q, x;

         scanf("%d%d%d", &N, &p, &q);

         memset(num, , sizeof(num));

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

         {

             scanf("%d", &x);

             num[x] = i;

         }

         int n = ;

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

         {

             scanf("%d", &x);

             if(num[x])

                 s[n++] = num[x];

         }

         //求s[1]...s[n]的LIS

         dp[] = s[];

         int len = ;

         for(int i = ; i <= n; ++i)

         {

             int left = , right = len;

             while(left <= right)

             {

                 int mid = (left + right) / ;

                 if(dp[mid] < s[i])

                     left = mid + ;

                 else

                     right = mid - ;

             }

             dp[left] = s[i];

             if(left > len)

                 ++len;

         }

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

     }

     return ;

 }

代码君

大白书里面用到了lower_bound函数

函数介绍

lower_bound()返回一个 iterator 它指向在[first,last)标记的有序序列中可以插入value，而不会破坏容器顺序的第一个位置，而这个位置标记了一个大于value 的值。

效果是一样的

 //#define LOCAL

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int INF = ;

 const int maxn =  * ;

 int num[maxn], s[maxn], g[maxn], d[maxn];

 int main(void)

 {

     #ifdef LOCAL

         freopen("10635in.txt", "r", stdin);

     #endif

     int T, kase;

     scanf("%d", &T);

     for(kase = ; kase <= T; ++kase)

     {

         int N, p, q, x;

         scanf("%d%d%d", &N, &p, &q);

         memset(num, , sizeof(num));

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

         {

             scanf("%d", &x);

             num[x] = i;

         }

         int n = ;

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

         {

             scanf("%d", &x);

             if(num[x])

                 s[n++] = num[x];

         }

         //求s[1]...s[n]的LIS

         for(int i = ; i <= n; ++i)

             g[i] = INF;

         int ans = ;

         for(int i = ; i < n; ++i)

         {

             int k = lower_bound(g+, g+n+, s[i]) - g;

             d[i] = k;

             g[k] = s[i];

             ans = max(ans, d[i]);

         }

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

     }

     return ;

 }

代码君

巴特西

UVa 10635 (LIS+二分) Prince and Princess

函数介绍

最新文章

热门文章