大佬帮忙看看
查看原帖
大佬帮忙看看
314588
cybercsc楼主2020/7/25 23:03

随便找的一个LIS的模板改了改,不知道为什么当两个序列相同的时候答案总是差一个

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define maxn 100000+100
#define memset(a,b) memset(a,b,sizeof(a))
using namespace std;
int indp1[maxn],indp2[maxn],dp[maxn];
int main()
{
    int n,tp,len=0;
    cin>>n;
    memset(dp,INF);
    for(int i=1;i<=n;i++){cin>>tp;indp1[tp]=i;}
    for(int i=1;i<=n;i++){cin>>tp;indp2[i]=indp1[tp];}
    dp[0]=0;
    for(int i=1;i<=n;i++){
        int pos=lower_bound(dp+1,dp+n+1,indp2[i])-dp;
        dp[pos]=indp2[i];
    }
    cout<<lower_bound(dp+1,dp+n+1,INF)-dp-1;
    return 0;
}

2020/7/25 23:03
加载中...