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

2023-11-12 23:51:04

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：

输入样例2：

5
1 2 3 5 4
1 2 3 4 5

输出样例2：

++++

思路：第一眼没看数据范围，以为就是个简单的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;
}

码农公寓