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

2014-10-20
竞赛题解 / 动态规划
FZOJ

描述 Description

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

输入格式 InputFormat

第一行一个整数，表示 N。
第二行 N 个整数，表示 A 序列。
第三行 N 个整数，表示 B 序列。

输出格式 OutputFormat

输出仅有一个整数，为这个子序列 l 的最大长度。

样例输入 SampleInput

5
1 2 4 3 5
5 2 3 4 1

样例输出 SampleOutput

2

来源 Source

2014-10-4 NOIP 模拟赛 by lwher

FZOJ 1553

代码 Code

类似于离散的思想，先找出 a 序列每个数在 b 序列中的对应位置，然后求 LIS 即可。

#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;
}