洛谷P1439
作者:
顽童
,
2022-08-03 21:24:58
,
所有人可见
,
阅读 190
随便记一下这个方法
https://www.luogu.com.cn/problem/solution/P1439
(本质为贪心)
用数组 mp 记录 a 序列中每一数字的位置下标
再根据 mp 得到 b 序列相对于 a 序列的位置下标,用 d 数组记录
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N], b[N], mp[N], d[N];
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i], mp[a[i]]=i;
for(int i=1;i<=n;i++) cin>>b[i];
int len=0;
for(int i=1;i<=n;i++)
{
if(mp[b[i]]>d[len]) d[++len]=mp[b[i]];
else
{
int p=lower_bound(d+1,d+1+len,mp[b[i]])-d;
d[p]=mp[b[i]];
}
}
cout<<len<<endl;
return 0;
}