题解 P1439 【【模板】最长公共子序列】

· · 题解

看了看其他人写的题解，感觉有点冗杂，我想以最简单，通俗得写一下自己的理解，希望大家能得到我的帮助！

首先看到这道题很容易一下就想到dp（n^2），但是看看数据范围，放弃dp，再看一看它题目给出的，这两串数都是1到n的全排列，说白了就上下两个串中的元素都是相同的，只有顺序不同而已，那么知道这个，我们又怎么来解决这道题呢？

我们可以以第一个串为标准，用第二个串来匹配第一个串，看能匹配多少，所以，其实第一个串的每个数字其实影响不大，只有知道它对应了第二串的哪个数字就好了，那么我们为什么不把他给的串重新定义一下？

比如他的样例：3 2 1 4 5 我们把他变成 1 2 3 4 5 用一个数组记录一下每个数字变成了什么，相当于离散化了一下3-1；2-2；1-3；4-4；5-5；

现在我们的第二串1 2 3 4 5 按我们离散化的表示：3 2 1 4 5

可能有些人已经懂了，我们把第一个串离散化后的数组是满足上升，反过来，满足上升的也就是满足原串的排列顺序的，（如果你不懂的话可以多看几遍这个例子）O(∩_∩)O~

好了 ，现在的问题就变成了求一个最长不下降序列！好了！解决完成！

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
int a1[100010],a2[100010];
int belong[100010];
int f[100010],b[100010],len;
int main()
{
    freopen("a.in","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a1[i]);
        belong[a1[i]]=i;
    }
    for(int i=1;i<=n;i++)
    scanf("%d",&a2[i]);
    for(int i=1;i<=n;i++)
    {
        if(belong[a2[i]]>b[len])
        {
            b[++len]=belong[a2[i]];
            f[i]=len;
            continue;
        }
        int k=lower_bound(b+1,b+len+1,belong[a2[i]])-b;
        b[k]=belong[a2[i]];
        f[i]=k;
    }
    printf("%d\n",len);
    return 0;
}