「NOIP模拟赛」球的序列
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
题解
将a[i]在b数组中的位置记为c[i]
求c的最长上升子序列
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<map> #include<vector> #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); 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,ans; int v[50005],a[50005]; int best[50005]; int find(int x) { int t=0,l=1,r=ans; while(l<=r) { int mid=(l+r)>>1; if(best[mid]<x)l=mid+1,t=mid; else r=mid-1; } return t; } void dp() { memset(best,127/3,sizeof(best)); best[0]=0; for(int i=1;i<=n;i++) { int t=find(v[i])+1; best[t]=min(best[t],v[i]); ans=max(ans,t); } } int main() { //freopen("formation.in","r",stdin); //freopen("formation.out","w",stdout); n=read(); for(int i=1;i<=n;i++)a[read()]=i; for(int i=1;i<=n;i++)v[i]=a[read()]; dp(); printf("%d",ans); return 0; } |
Subscribe
计数器 9789998
OI 课件=>
OI 课件=>