题目内容

P1439

大意:给出 1-n 的两个排列,求他们的 LCS

解题思路

O(n^2) 的算法依然十分好想:设 f_{i,j} 为以 a_ib_j 结尾的 LCS 的最大长度,具体的转移考虑两种情况:

f_{i,j}=
\begin{cases}
\max\lbrace f_{i-1,j},f_{i,j-1} \rbrace\quad(a_i\neq b_j)\
\max\lbrace f_{i,j},f_{i-1,j-1}+1\rbrace\quad(a_i=b_j)
\end{cases}

分别是这一位上的两个序列的数字相等和不相等的情况,然而当 n=10^5 时空间和时间都会炸掉,所以我们需要更高效的算法。

这里使用阮行止老师的解释:

关于为什么可以转化成LIS问题,这里提供一个解释。
A:3 2 1 4 5
B:1 2 3 4 5
我们不妨给它们重新标个号:把3标成a,把2标成b,把1标成c……于是变成:
A:a b c d e
B:c b a d e
这样标号之后,LCS长度显然不会改变。但是出现了一个性质:
两个序列的子序列,一定是A的子序列。而A本身就是单调递增的。
因此这个子序列是单调递增的。
换句话说,只要这个子序列在B中单调递增,它就是A的子序列。

所以我们发现,只要将 a_i 对应到 i 上之后,求 LCS 就变成了求 b 的 LIS 问题了,代码如下:

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int maxn=1e5+5;
int n,a[maxn],b[maxn],f[maxn];

int main()
{
    scanf("%d",&n);
    for(int i=1,x;i<=n;++i)
    {
        scanf("%d",&x);
        a[x]=i;//将a[i]与i对应起来
    }
    for(int i=1,x;i<=n;i++)
    {
        scanf("%d",&x);
        b[i]=a[x];//直接处理b
    }
    memset(f,0x7fffffff,sizeof(f));
    int len=1;
    f[1]=b[1];
    for(int i=2;i<=n;i++)//常规求 LIS
    {
        if(b[i]>f[len])
            f[++len]=b[i];
        else
        {
            int p=lower_bound(f+1,f+len+1,b[i])-f;
            f[p]=b[i];
        }
    }
    printf("%d\n",len);
    return 0;
}
最后修改日期:2020年3月7日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。