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=;

    char last=' ',ch=getchar();

    while(ch<''||ch>'') last=ch,ch=getchar();

    while(ch>=''&&ch<='') ans=ans*+ch-'',ch=getchar();

    if(last=='-') ans=-ans;

    return ans;

}

const int maxn=1e5+;

int n,a[maxn],pos[maxn],y;

int d[maxn],len=;

int main()

{

    n=read();

    for(int i=;i<=n;i++)

       a[i]=read(),pos[a[i]]=i;

    for(int i=;i<=n;i++)

    {

        y=read();

        int now=pos[y];

        if(now>d[len]) d[++len]=now;

        else d[lower_bound(d+,d+len+,now)-d]=now;

    }

    printf("%d",len);

    return ;

}

巴特西

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

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

最新文章

热门文章