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

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

这道题的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);
}

• 帮你找了个相似的问题, 你可以看下: https://ask.csdn.net/questions/7514556

您好，我是有问必答小助手，您的问题已经有小伙伴帮您解答，感谢您对有问必答的支持与关注！
PS：问答VIP年卡 【限时加赠：IT技术图书免费领】，了解详情>>> https://vip.csdn.net/askvip?utm_source=1146287632