Codevs 2185【模板】最长公共上升子序列

题目描述 Description

熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。小沐沐先让奶牛研究了最长上升子序列，再让他们研究了最长公共子序列，现在又让他们要研究最长公共上升子序列了。
小沐沐说，对于两个串A，B，如果它们都包含一段位置不一定连续的数字，且数字是严格递增的，那么称这一段数字是两个串的公共上升子串，而所有的公共上升子串中最长的就是最长公共上升子串了。
奶牛半懂不懂，小沐沐要你来告诉奶牛什么是最长公共上升子串。不过，只要告诉奶牛它的长度就可以了。

输入描述 Input Description

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

输出描述 Output Description

输出长度。

样例输入 Sample Input

4
2 2 1 3
2 1 2 3

样例输出 Sample Output

2

数据范围及提示 Data Size & Hint

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

 

/*

dp[i][j]表示以s1的第i个元素和s2的第j个元素结尾的LCIS长度

1、若a[i]<a[j]，则dp[i][j]=dp[i-1][j]

2、若a[i]==a[j]，则dp[i][j]=max(dp[i][k])+1, k=1->j

朴素的求解LCIS(n^3)：

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

        for(int j=1;j<=m;++j)

        {

            dp[i][j]=dp[i-1][j];

            if(a[i]==a[j])

            {

                int tmp=0;

                for(int k=1;k<j;++k)

                    if(a[j]>a[k])

                        tmp=max(tmp,dp[i-1][k]);

            }

        }

可以发现，tmp在++j的时候就可以被算出来，所以我们可以省掉枚举k的那重循环，这样就变成了O(n^2)。

*/

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

const int N=;

int n;

int a[N],dp[N];

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n<<;scanf("%d",&a[i]),++i);

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

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

        {

            if(a[i]>a[j]&&len<dp[j])

                len=dp[j];

            else if(a[i]==a[j])

                dp[j]=len+;

        }

    int ans=*max_element(dp+n+,dp+n*+);

    printf("%d",ans);

    return ;

}