解题报告 P1439 【模板】LCS

题目内容

P1439

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

解题思路

O(n^2) 的算法依然十分好想：设 f_{i,j} 为以 a_i 和 b_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;
}