A Daily Topic # 4 最长公共子序列(LCS/LIS/贪心)

A Daily Topic # 5

最长公共子序列

给出两个长度为 n 的整数序列,求它们的最长公共子序列(LCS)的长度,保证第一个序列中所有元素都不重复。

注意:

  • 第一个序列中的所有元素均不重复。
  • 第二个序列中可能有重复元素。
  • 一个序列中的某些元素可能不在另一个序列中出现。

输入格式

第一行包含一个整数 n。

接下来两行,每行包含 n 个整数,表示一个整数序列。

输出格式

输出一个整数,表示最长公共子序列的长度。

数据范围

1≤n≤1e6,
序列内元素取值范围 [1, 1e6]。

输入样例1:

5
1 2 3 4 5
1 2 3 4 5

输出样例1:

5

输入样例2:

5
1 2 3 5 4
1 2 3 4 5

输出样例2:

4

++++

思路:第一眼没看数据范围,以为就是个简单的LCS DP问题,然后看到数据范围知道不可取。然后有个很重要的条件就是第一个序列是不重复的一个序列,所以这就使得序列二的数字出现在序列一中的位置是固定的。我们拿输入样例2来讲:

其中tar数组表示序列二的数字在序列一中出现的位置。

序列1: 1 2 3 5 4

序列2: 1 2 3 4 5

tar数组:1 2 3 5 4

然后我们观察tar数组,每个数字代表的是位置下标,如果我们找到tar数组的最长上升子序列长度,1 2 3 4 或者1 2 3 5。因为是上升的,所以得到的在序列一中的位置的数字一定也是如此的次序,又因为tar数组是描述序列二的性质的数组,所以其次序一定是从左到右的。因此我们就可以把LCS问题转化成LIS问题,即求tar数组的最长上升子序列问题。但是观察n的范围是[1, 1e6],通过DP求最长上升子序列是O(n²)的复杂度,因此不可取。应该用基于贪心的O(nlogn)的解法。

代码:

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1000010;

int tar[N];
int n;
int q[N];

int main()
{
    scanf("%d", &n);
    int x;
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%d", &x);
        tar[x] = i;
    }
    
    int len = 0;
    //基于贪心通过二分解决
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%d", &x);
        int k = tar[x];
        
        if (!k) continue;//跳过没有出现过的数据
        int l = 0, r = len;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (q[mid] < k) l = mid;
            else r = mid - 1;
        }
        
        len = max(len, r + 1);
        q[r + 1] = k;
    }
    
    printf("%d\n", len);
    
    return 0;
}

上一篇:Daily Coding Problem


下一篇:Daily Codeforces 计划 训练时录