关于#c语言#的问题：洛谷P1438最长公共子序列与动态规划有关错误信息如图找出错误并给出解决方案通过测试

Question

洛谷P1438最长公共子序列与动态规划有关
错误信息如图
找出错误并给出解决方案通过测试

Answer 1

这道题的n高达1e5，两次循环下来肯定会超时的
两序列长度相同并且都是1-n的排列，因此可以进行优化将时间复杂度降为nlogn，数组降为1维。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],b[N],c[N],f[N];
int len=1;
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
    scanf("%d",&a[i]);
    c[a[i]]=i;
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&b[i]);
        b[i]=c[b[i]];
    }
    f[1]=b[1];
    for(int i=2;i<=n;i++)
    {
        if(f[len]<b[i])
        f[++len]=b[i];
        else
        f[lower_bound(f+1,f+len+1,b[i])-f]=b[i];
    }
    printf("%d",len);
}