首页 > 代码库 > UVa 10635 (LIS+二分) Prince and Princess

UVa 10635 (LIS+二分) Prince and Princess

2024-07-16 09:53:11   229人阅读

题目的本意是求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

在这里再复习一遍

 1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7  8 const int maxn = 250 * 250; 9 int num[maxn], s[maxn], dp[maxn];10 11 int main(void)12 {13     #ifdef LOCAL14         freopen("10635in.txt", "r", stdin);15     #endif16 17     int T, kase;18     scanf("%d", &T);19     for(kase = 1; kase <= T; ++kase)20     {21         int N, p, q, x;22         scanf("%d%d%d", &N, &p, &q);23         memset(num, 0, sizeof(num));24         for(int i = 1; i <= p+1; ++i)25         {26             scanf("%d", &x);27             num[x] = i;28         }29         int n = 1;30         for(int i = 1; i <= q+1; ++i)31         {32             scanf("%d", &x);33             if(num[x])34                 s[n++] = num[x];35         }36         //求s[1]...s[n]的LIS37         dp[1] = s[1];38         int len = 1;39         for(int i = 2; i <= n; ++i)40         {41             int left = 1, right = len;42             while(left <= right)43             {44                 int mid = (left + right) / 2;45                 if(dp[mid] < s[i])46                     left = mid + 1;47                 else48                     right = mid - 1;49             }50             dp[left] = s[i];51             if(left > len)52                 ++len;53         }54 55         printf("Case %d: %d\n", kase, len);56     }57     return 0;58 }
代码君

 

大白书里面用到了lower_bound函数

函数介绍

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

效果是一样的

 1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7  8 const int INF = 1000000000; 9 const int maxn = 250 * 250;10 int num[maxn], s[maxn], g[maxn], d[maxn];11 12 int main(void)13 {14     #ifdef LOCAL15         freopen("10635in.txt", "r", stdin);16     #endif17 18     int T, kase;19     scanf("%d", &T);20     for(kase = 1; kase <= T; ++kase)21     {22         int N, p, q, x;23         scanf("%d%d%d", &N, &p, &q);24         memset(num, 0, sizeof(num));25         for(int i = 1; i <= p+1; ++i)26         {27             scanf("%d", &x);28             num[x] = i;29         }30         int n = 0;31         for(int i = 1; i <= q+1; ++i)32         {33             scanf("%d", &x);34             if(num[x])35                 s[n++] = num[x];36         }37         //求s[1]...s[n]的LIS38         for(int i = 1; i <= n; ++i)39             g[i] = INF;40         int ans = 0;41         for(int i = 0; i < n; ++i)42         {43             int k = lower_bound(g+1, g+n+1, s[i]) - g;44             d[i] = k;45             g[k] = s[i];46             ans = max(ans, d[i]);47         }48         printf("Case %d: %d\n", kase, ans);49     }50     return 0;51 }
代码君

 


联系
我们