球的序列(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序列。

样例输入

1 2 4 3 5

5 2 3 4 1

样例输出

样例说明

L可以是{2,3}，也可以是{2,4}

数据范围:

40% N<=5000

100% N<=50000

/*

  一看题目，没多想就以为是最长公共子序列，无奈n^2做法不给力，40分

  经某大神提醒，不用最长公共子序列，因为第二个数列中的数和第一个中的数一样的，所以先预处理处第二个数列中的数在第一个数列中的位置，然后跑最长上升子序列。

*/

#include<cstdio>

#include<iostream>

#define M 50010

using 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=;i<=n;i++)

      scanf("%d",&a[i]),num[a[i]]=i;

    for(int i=;i<=n;i++)

    {

        int x;

        scanf("%d",&x);

        b[i]=num[x];

    }

    c[++len]=b[];

    for(int i=;i<=n;i++)

    {

        int pos=lower_bound(c+,c+len+,b[i])-c;

        if(pos>len)++len;

        c[pos]=b[i];

    }

    printf("%d",len);

    return ;

}

巴特西

球的序列(formation.*)

最新文章

热门文章