「NOIP模拟赛」球的序列

2014年10月4日3,5230

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的最长上升子序列

 

avatar
  Subscribe  
提醒