欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【模板】最长公共子序列

程序员文章站 2024-01-14 16:53:04
...

洛谷P1439为例
n可以开到1e5……TLE+MLE(编译都过不了)
读入a数组后哈希一波,然后将b数组的值在哈希数组里找到对应值并替换,于是变成了求b数组最长上升子序列(玄学……)可以使用二分,时间复杂度o(nlogn)AC

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
using namespace std;
const int N=1e5+5;
int a[N],f[N],b[N],len[N];
int read()
{
    char c=getchar();
    int x=0;
    while(!isdigit(c))c=getchar();
    while(isdigit(c))
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}
int main()
{
    //freopen("in.txt","r",stdin);
    int i,n,k=0;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        a[i]=read();
        f[a[i]]=i;
    }
    for(i=1;i<=n;i++)
    {
        b[i]=read();
        b[i]=f[b[i]];
    }
    for(i=1;i<=n;i++)
    {
        if(b[i]>len[k])len[++k]=b[i];
        else{
            int l=1,r=k;
            while(l<=r)
            {
                int mid=l+r>>1;
                if(len[mid]<b[i])l=mid+1;
                if(len[mid]>b[i])r=mid-1;
            }
            len[l]=b[i];
        }
    }
    printf("%d",k);
    return 0;
}
相关标签: 线性DP

上一篇: st表求lca

下一篇: C—判断素数