N个编号为1-n的球,每个球都有唯一的编号。这些球被排成两种序列,分别为A、B序列,现在需要重新寻找一个球的序列l,对于这个子序列l中任意的两个球,要求j,k(j<k),都要求满足lj在A中位置比lk在A中位置靠前,却lj在B中位置比lk在B中位置靠前,请你计算这个子序列l的最大长度。
输入:
第一行一个整数,表示N。
第二行N个整数,表示A序列。
第三行N个整数,表示B序列。
青岛版数学摸球游戏课堂实录。
样例输入
5
1 2 4 3 5
5 2 3 4 1
样例输出
2
样例说明
L可以是{2,3},也可以是{2,4}
数据范围:
40% N<=5000
100% N<=50000
/* 最长上升子序列 */ #include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<cmath> #include<queue> #define fo(i,l,r) for(int i = l;i <= r;i++) using namespace std; const int maxn = 50050; inline int read(){char ch=getchar();int f=1,x=0;while(!(ch>='0'&&ch<='9')){if(ch=='-')f=-1;ch=getchar();};while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();};return x*f; } int n,a[maxn],b[maxn],tran[maxn],d[maxn],g[maxn]; int main(){n = read();fo(i,1,n) a[i] = read();fo(i,1,n){b[i] = read();tran[b[i]] = i;}fo(i,1,n){b[tran[a[i]]] = i;}memset(g,127/3,sizeof(g));int ans = 0;fo(i,1,n){int k = lower_bound(g+1,g+1+n,b[i]) - g;d[i] = k;g[k] = b[i];ans = max(ans,d[i]);}cout<<ans;return 0; }