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

小邱 · 2022-03-20 17:08:18 · 个人记录

观察数据范围

说明/提示

• 对于 50% 的数据，n \le 10^3
• 对于 100% 的数据， n \le 10^5

50pt

显然，50分的数据可以用O(n^2)的时间复杂度

采用DP，令a数组为p_1，b数组为p_2

看数据， n \le 10^5 ，肯定是O(N log N)或者是O(N)的时间复杂度，O(N)不可能，所以选择前者

我们采用离散化，初始化：d[a[i]]=i

因为两个序列都是1\sim n，所以如果把b[i]映射到d[a[i]]，之后这个问题就变成了最长不下降子序列的问题

我们用样例来进行解释（用到的数组名称都是我代码里面的）：

5 
3 2 1 4 5
1 2 3 4 5

对a数组进行离散化后得到（下面一行是分别对应的真正数）

b数组离散化后：{3,2,1,4,5}

仔细思考一下，为什么是最长不下降子序列而不是下降？

因为离散化本质上就是把数值对应成了位置，只有当b数组不下降时才能使得有公共子序列

其实求最长上升子序列也可以，都一样

接下来就是求最长不下降子序列的问题了：

普通算法是O(n^2)

显然和前面50pt没啥区别，所以我们要用二分查找和贪心的思想来优化，时间复杂度为O(nlogn)

具体策略如下（d数组还是离散化的数组）：

数组c表示目前的最长不下降子序列，长度为m

• 如果第i个数大于等于c的末尾，即d[b[i]]\geq c[m]：很明显能够直接加入到c的末尾

• 如果小于，那么用二分查找找出c数组中第一个\geq d[b[i]]的数，将他替换掉，这里就是贪心了，这样能够使得c数组前面的数变小，如果前面的数变小了，后面是不是更容易添加新的数了呢？肯定如此

  这样做不会影响到最终的长度和后面的操作（大家可以自行脑补），但是会影响求出的子序列本身，因此这可能不是答案，但是c的长度m就是最长不下降子序列的长度

  要是要求输出具体的子序列，可能就需要中间加上答案的复制或保护

通过离散化和优化最长不下降子序列，这道题就完成了，建议配合代码食用

#include<bits/stdc++.h>
typedef unsigned long long ull;
typedef long long ll;
using namespace std;
const int N=100005;
int a[N],b[N],c[N],d[N];
int main()
{
    int m=0,i,k,n;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        d[a[i]]=i;//离散化
    }
    for(i=1;i<=n;i++)
    {
        scanf("%d",&b[i]);
    }
    for(i=1;i<=n;i++)
    {
        if(d[b[i]]>=c[m])//第一种情况
        {
            m++;
            c[m]=d[b[i]];
            continue;
        }
        k=lower_bound(c+1,c+1+m,d[b[i]])-c;//这个函数是的意思是找出c数组中第一个>=d[b[i]]的位置（因为用到二分，所以数组要求有序）
        c[k]=d[b[i]]; //替换
    }
    printf("%d",m);
    return 0;
}