【Tyvj1071】LCIS

2014-05-15
竞赛题解 / 动态规划
TYVJ

描述 Description

熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。小沐沐先让奶牛研究了最长上升子序列，再让他们研究了最长公共子序列，现在又让他们要研究最长公共上升子序列了。

小沐沐说，对于两个串 A，B，如果它们都包含一段位置不一定连续的数字，且数字是严格递增的，那么称这一段数字是两个串的公共上升子串，而所有的公共上升子串中最长的就是最长公共上升子串了。

奶牛半懂不懂，小沐沐要你来告诉奶牛什么是最长公共上升子串。不过，只要告诉奶牛它的长度就可以了。

1<=N<=3000，A，B 中的数字不超过 maxlongint。

输入格式 InputFormat

第一行 N，表示 A，B 的长度。
第二行，串 A。
第三行，串 B。

输出格式 OutputFormat

输出长度。

样例输入 SampleInput

10
1 5 3 6 3 2 7 3 6 2
9 6 2 3 1 5 3 3 6 1

样例输出 SampleOutput

3

Tyvj 1071

代码 Code

LCIS… 一维数组动规方程用 f[j] 表示 a 的前某个串与 b 的前 j 个串的最长公共上升子序列的长度。z 维护可选子序列的最大值。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <cmath>
using namespace std;
int a[5000],b[5000];
int f[5000];
int i,j,t,n,m,l,r,k,z,y,x,ans;
int main()
{
    scanf("%d",&n);
    for (i=1;i<=n;i++) scanf("%d",&a[i]);
    for (i=1;i<=n;i++) scanf("%d",&b[i]);
    memset(f,0,sizeof(f));
    for (i=1;i<=n;i++)
    {
        z=0;
        for (j=1;j<=n;j++)
        {
            if (a[i]>b[j]) z=max(z,f[j]);
            if (a[i]==b[j]) f[j]=z+1;
        }
    }
    ans=0;
    for (i=1;i<=n;i++) ans=max(ans,f[i]);
    printf("%d\n",ans);
    return 0;
}