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

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

题解

1.RE的暴力DP O(n²)

我们设dp[i][j]表示，S串的第i个前缀和T串的第j个前缀的最长公共子序列。

◦          分情况：

◦          如果S[i]==T[j]，dp[i][j]=dp[i-1][j-1]+1;

◦          如果S[i]!=T[j]，dp[i][j]=max(dp[i-1][j],dp[i][j-1]);

◦          最后答案就是dp[n][m]

◦          对于dp[i][j]：

◦          如果，两个串最后一个位置相同，这两个位置一定在公共子序列中。

◦          那么我们只需要求出S的i-1前缀和T的j-1前缀的最长上升子序列就可以了，而这个就是把问题化小。

◦          如果最后一个位置不相同，那么两个位置一定不能匹配，所以肯定是另外两种情况选最大的。

2.正解  O(nlogn)

这道题目是求两个全排列的LCS

那么对于排列 b 中的每一个数字都会在排列 a 中出现，只是出现的顺序不同

那么我们设置一个 pos [ ] 数组，记录下 a 序列中每个数字出现的位置

然后输入  b  序列，那么找出 b 中的每个数字对应 a 中数字出现的位置

为什么是求b对应的pos数组的LIS呢？？？

给定a数组，我们求LCS，一定是拿着b数组从前往后一一比对的，b中数字的在a中出现的顺序如果是递增的，那么就有机会顺着前面的位置接下去，扩展LCS

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<queue>

using namespace std;

inline int read()
{
    int ans=0;
    char last=' ',ch=getchar();
    while(ch<'0'||ch>'9') last=ch,ch=getchar();
    while(ch>='0'&&ch<='9') ans=ans*10+ch-'0',ch=getchar();
    if(last=='-') ans=-ans;
    return ans;
}

const int maxn=1e5+10;
int n,a[maxn],pos[maxn],y;
int d[maxn],len=0;

int main()
{
    n=read();
    for(int i=1;i<=n;i++) 
       a[i]=read(),pos[a[i]]=i;
    for(int i=1;i<=n;i++)
    {
        y=read();
        int now=pos[y];
        if(now>d[len]) d[++len]=now;
        else d[lower_bound(d+1,d+len+1,now)-d]=now; 
    }
    printf("%d",len);
    return 0;
}