# [FZOJ1553] 球的序列 (formation.*)

## 描述 Description

N 个编号为 1-n 的球，每个球都有唯一的编号。这些球被排成两种序列，分别为 A、B 序列，现在需要重新寻找一个球的序列 l，对于这个子序列 l 中任意的两个球，要求 j,k(j

5
1 2 4 3 5
5 2 3 4 1

2

## 来源 Source

2014-10-4 NOIP 模拟赛 by lwher

FZOJ 1553

## 代码 Code

``````#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
int i,j,t,n,m,l,r,k,z,y,x;
int a[50005],b[50005],c[50005],d[50005];
inline int lis(int *a)
{
int i,j,t;
memset(d,0,sizeof(d));
m=1;d[m]=a[m];
for (i=m+1;i<=n;i++)
{
if (a[i]>d[m])
{
d[++m]=a[i];
continue;
}
t=lower_bound(d+1,d+m+1,a[i])-d;
d[t]=a[i];
}
return m;
}
int main()
{
freopen("formation.in","r",stdin);
freopen("formation.out","w",stdout);
scanf("%d",&n);
for (i=1;i<=n;i++) scanf("%d",&a[i]);
for (i=1;i<=n;i++) scanf("%d",&b[i]),c[i]=b[i];
sort(c+1,c+n+1);
for (i=1;i<=n;i++) t=lower_bound(c+1,c+n+1,b[i])-c,d[t]=i;
for (i=1;i<=n;i++) t=lower_bound(c+1,c+n+1,a[i])-c,a[i]=d[t];
printf("%d\n",lis(a));
return 0;
}``````