首页 > 代码库 > 球的序列(formation.*)
球的序列(formation.*)
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
/* 一看题目,没多想就以为是最长公共子序列,无奈n^2做法不给力,40分 经某大神提醒,不用最长公共子序列,因为第二个数列中的数和第一个中的数一样的,所以先预处理处第二个数列中的数在第一个数列中的位置,然后跑最长上升子序列。 */#include<cstdio>#include<iostream>#define M 50010using namespace std;int a[M],b[M],num[M],c[M],len,n;int main(){ //freopen("jh.in","r",stdin); freopen("formation.in","r",stdin); freopen("formation.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]),num[a[i]]=i; for(int i=1;i<=n;i++) { int x; scanf("%d",&x); b[i]=num[x]; } c[++len]=b[1]; for(int i=2;i<=n;i++) { int pos=lower_bound(c+1,c+len+1,b[i])-c; if(pos>len)++len; c[pos]=b[i]; } printf("%d",len); return 0;}
球的序列(formation.*)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。