60pts求助

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

zhaodexuan20121211 @ 2024-05-18 08:27:08

#include<bits/stdc++.h>
using namespace std;
long long n,a[100005],b[100005],dp[100005],d[100005],maxx; 
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=n;i++)
    {
        cin>>b[i];
        d[b[i]] = i;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<i;j++)
        {
            if(d[a[i]]>d[a[j]])
            {
                dp[i] = max(dp[i],dp[j]+1);
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        maxx = max(maxx,dp[i]);
    }
    cout<<maxx;
    return 0;
}

玄一关


by I_Love_DS @ 2024-05-18 09:23:38

@zhaodexuan20121211 双重循环?

需用二分优化。 ~~尽管我不会~~

by OldDriverTree @ 2024-05-18 09:34:07

@liuruiqing 就是 LIS 的 nlogn 做法啊


by I_Love_DS @ 2024-05-18 09:41:16

@OldDriverTree 可是我是蒟蒻啊

我啥也不是

关于 dp,它复活了


by zhaodexuan20121211 @ 2024-10-09 18:23:41

@OldDriverTree 好几个月了,已关,此帖结


|