2019-sjtu最长公共子序列

本题和acwing的这道题一模一样最长公共子序列

相比于普通的LCS问题这道题的特点是：

第一个序列元素不重复，第二个序列元素可以重复。

先说结论： LCS和LIS问题是可以相互转化的，转化的关键是只要有一个序列满足所有元素不重复即可

思路： alt

假设A存储第一个序列，B存储第二个序列，B'存储B中的元素在A中的位置。

由此可知，B中的元素B[i]和B'的下标i是一一对应的
B'[i]表示B[i]在A中的位置

看图，假设在B'中存在一个长度为4的递增的序列，即：

这四个元素的下标i是递增的（在B中是递增的）
这四个元素的值B'[i]是递增的（在A中是递增的）

这里完成了一个LCS到LIS的映射关系，B'中的递增序列满足A-B中的一个公共子序列。

同理，反过来 A-B中的一个最长公共子序列也可以映射为B'中的一个递增子序列

由此，我们完成了LCS-LIS的转化

细节实现：

		for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);//读入第一行数字
            id[a[i]]=i;//在id数组中标明第一个序列的每个元素的位置
        }

将第一个序列读入a[]数组，并在id中表明a中元素出现位置

        for(int i=1;i<=n;i++)
        {
            scanf("%d",&b[i]);//读入第二个序列
            b[i]=id[b[i]];//数组b存储第二个序列中的元素在第一个序列a中的位置，若a中不存在该元素，则b[i]为0
        }

将第二个序列读入b[]数组，并在b数组中标记该元素在a中的位置（这里的b[]起到了B'数组的作用）

这里b[i]=id[b[i]];比较难理解，其实是隐藏了一层关系

我们先将第二个序列读入b[i]，然后又将b[i]覆盖为第二个序列的第i个元素在a中的位置

所以此时的b[i]：i表示序列b中的第i个元素，b[i]表示序列b中的第i个元素在a中的位置

所以数组b的下标和值完成了LCS-LIS的映射。现在问题变成了求数组b的LIS问题

又因为数值范围1e6，若采用朴素dp，时间复杂度O(n^2)，则会TLE，因此采用贪心改进的LIS解法：

利用LIS这一vector来存储每个长度的上升子序列的末尾最小值

        for(int i=1;i<=n;i++)
        {
            if(b[i]==0) continue;//未在a中出现的数字

            if(!LIS.size()||b[i]>LIS.back()) LIS.push_back(b[i]);//b[i]大于LIS末位值或LIS为空，直接加入LIS尾部

            int id=lower_bound(LIS.begin(),LIS.end(),b[i])-LIS.begin();//二分法找到LIS中第一个大于等于b[i]的位置，并将其替换为b[i]
            LIS[id]=b[i];
        }

最后返回LIS的长度，即为所求LCS的长度

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

const int N=1e6+10;
int a[N],b[N],id[N];

int n;


int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        memset(id,0,sizeof id);//每次更新id数组
        vector<int> LIS;//存储LIS的向量
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);//读入第一行数字
            id[a[i]]=i;//在id数组中标明第一个序列的每个元素的位置
        }

        for(int i=1;i<=n;i++)
        {
            scanf("%d",&b[i]);//读入第二个序列
            b[i]=id[b[i]];//数组b存储第二个序列中的元素在第一个序列a中的位置，若a中不存在该元素，则b[i]为0
        }

        //这里为LIS的贪心解法：用一个递增序列存储所有的最长上升子序列的最小的末位元素值
        for(int i=1;i<=n;i++)
        {
            if(b[i]==0) continue;//未在a中出现的数字

            if(!LIS.size()||b[i]>LIS.back()) LIS.push_back(b[i]);//b[i]大于LIS末位值或LIS为空，直接加入LIS尾部

            int id=lower_bound(LIS.begin(),LIS.end(),b[i])-LIS.begin();//二分法找到LIS中第一个大于等于b[i]的位置，并将其替换为b[i]
            LIS[id]=b[i];
        }

        printf("%d",LIS.size());//输出LIS
        puts("");


    }
    return 0;
}