最长公共子序列

交大的机试还是猛啊!

题目描述

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

注意:

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

输入格式

第一行包含一个整数 n。

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

输出格式

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

数据范围

1≤n≤10^6,
序列内元素取值范围 [1,10^6]

输入样例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

题解

这道题目打眼一看是要解决最长公共子序列问题,但是我们仔细一瞧会发现题目的数据范围在[1,10^6],做场公共子序列需要O(n^2)的时间复杂度,显然这是无法满足要求的,那么怎么办呢?
题目中的注意是一个关键点。

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

当一个最长公共子序列问题中,其中一个子序列满足所有元素均不重复时,那么最长公共子序列问题可以转化成最长上升子序列问题。
证明如下:假设数组A表示第一个序列,且A中不存在重复元素,数组B表示第二个子序列,那么我们可以另开一个数组C表示B中元素在A中的对应位置,那么我们可以惊奇的发现,每一个数组A和数组B的公共子序列都会在数组C中对应一个上升序列,那么我们要求的数组A和数组B的最长公共子序列就对应于数组C中的最长上升子序列。
最长上升子序列的求解有两种方法。DP的方式是O(n^2)的复杂度,贪心的做法是O(nlogn)的复杂度。这里由于数据范围较大,因此应该选用贪心的做法。

求最长上升子序列贪心做法


这个序列是单调递增的证明如下,利用反证法证明。

那么,有上面的结论就有了一个特别好的性质。我们此时进来一个值x,那么这个x只需要更新最小末尾值刚好大于x的第一个上升子序列。为什么呢?除最小末尾值刚好大于x的第一个序列可以用前一个位置加上x更新外,不能更新。小于x的值,也无法被更新,如下图所述。

这样的话,我们就可以每次利用二分来找到可以更新的位置,然后边找边更新答案。
时间复杂度为O(nlogn)

代码

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

using namespace std;

const int N = 1000010;

int n;
int id[N], q[N];

int main()
{
    scanf("%d", &n);
    memset(id, -1, sizeof id);
    for (int i = 0; i < n; i ++ )
    {
        int x;
        scanf("%d", &x);
        id[x] = i;
    }

    int tt = 0;
    q[0] = -1;
    for (int i = 0; i < n; i ++ )
    {
        int x;
        scanf("%d", &x);
        int k = id[x];
        if (k == -1) continue;
        int l = 0, r = tt;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (q[mid] < k) l = mid;
            else r = mid - 1;
        }
        q[r + 1] = k;
        tt = max(tt, r + 1);
    }

    printf("%d\n", tt);
    return 0;
}

发表回复

您的电子邮箱地址不会被公开。