不懂就问

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

aaaaaaaawsl @ 2021-07-17 15:25:42

#include<iostream>
#include<cstdio>
using namespace std;
int a[100001],b[100001],map[100001],f[100001];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){scanf("%d",&a[i]);map[a[i]]=i;}
    for(int i=1;i<=n;i++){scanf("%d",&b[i]);f[i]=0x7fffffff;}
    int len=0;
    f[0]=0;
    for(int i=1;i<=n;i++)
    {
        int l=0,r=len,mid;
        if(map[b[i]]>f[len])f[++len]=map[b[i]];
        else 
        {
        while(l<r)
        {   
            mid=(l+r)/2;
            if(f[mid]>map[b[i]])r=mid;
            else l=mid+1; 
        }
        f[l]=min(map[b[i]],f[l]);
        }
    }
    cout<<len;
    return 0
}

看不懂第三个for循环,题解第一篇,主要是len,map,f的作用,求dl解答(我好菜啊

PS:其实题解区哪位dl没解释,我l,r也不懂

PPS:当然可能是我眼瞎,dbq


by ahawzlc @ 2021-07-17 15:50:11

这个我们今天zzy老师也讲了。

整个代码是对LCS的n\log n优化,前面将LCS转化为LIS问题(通过map数组表示a[i]在b[i]中的位置),随后对运用二分优化LIS的方法来优化LCS。

花姐姐是这么解释上述转化的。

最长公共子序列是按位向后比对的,所以a序列每个元素在b序列中的位置如果递增,就说明b中的这个数在a中的这个数整体位置偏后

len为f数组的有效位置,f就是dp数组,表示当前所记录的最长上升子序列末尾元素,这个是用来进行二分LIS优化的基础。

具体二分过程还是去看花姐姐的注释吧,讲得很明白。

(如果我有哪个地方理解错了还请指正)


|