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

cyborg · 2018-01-31 15:10:53 · 题解

假设ans[i]代表当公共最长子序列长度为i时所需要序列a的长度，那么ans当中，就是一个上升序列，方便二分查找，line[i]表示i这个数字在第一个序列中的位置。

每当读入第二个序列的数字m时，我们就在ans里用二分查找找到ans[r]<line[m]<ans[l]，接着就可以将ans[l]的值降低为line[m]的值。当然，如果说ans中最大的数小于line[m]，就可以给最长公共子序列长度加一

代码如下：

#include<cstdio>
#include<iostream>
using namespace std;
int main()
{
    //freopen("test.cpp","r",stdin);
    int n,m,line[100001]={0},ans[100001]={0},total=0;//total表示最长公共子序列长度
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>m;
        line[m]=i;//line[m]是m在第一个序列中的位置
    }
    for(int i=1;i<=n;i++)
    {
        cin>>m;
        int search=line[m];
        if(search>ans[total])ans[++total]=search;else
        {
            int l=0,r=total;
            while(l<=r)
            {
                int mid=ans[(l+r)/2];
                if(search<mid)r=(l+r)/2-1;else
                l=(l+r)/2+1;
            }
            ans[l]=search;//因为之前最长公共子序列长度为l时所需要的第一个序列的长度大于长度为l-1时再包括了数字m时（同样最长公共子序列长度为l）所需要第一个序列的长度
        }
    }
    cout<<total;
}