题目描述

其实，这道题目就是两大dp巨头的综合，即“最长上升子序列”与“最长公共子序列”，相信读者都了解这两道题的内容。
当然，这也就是我们这道题的重要突破口！

算法

(dp) $O(n^2)$

根据上面我的概述，可以发现，这道题目的基本算法方向已经确定–dp。
下面–高举“闫氏思考法”大旗：
1.状态表示：我们可以将f[i][j]定义为：所有由第一个序列的1~i个字母，和第二个序列的i~j个字母构成的公共上升子序列集合（以b[j]结尾），f[i][j]的值等于该集合的子序列中长度的最大值。
2.状态计算：
1.不包含a[i]：
maxn=f[i-1][j];//这个比较浅显，没有a[i]，最大值必然是f[i-1][j]
2.包含a[i]:
1.子序列只包含b[j]一个数，长度是1
2.子序列的倒数第二个数是b[k]的集合，最大长度是f[i-1][k]+1

时间复杂度

$O(n^2)$

C++ 代码

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
inline int read()
{
    int s=0,w=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')
            w=-w;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        s=s*10+c-'0';
        c=getchar();
    }
    return s*w;
}
const int N=3005;
int n,ans;
int a[N],b[N];
int f[N][N];
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
        a[i]=read();
    for(int i=1;i<=n;i++)
        b[i]=read();
    for(int i=1;i<=n;i++)
    {
        int maxn=1;
        for(int j=1;j<=n;j++)
        {
            f[i][j]=f[i-1][j];
            if(a[i]==b[j])
                f[i][j]=max(f[i][j],maxn);
            if(b[j]<a[i])
                maxn=max(maxn,f[i][j]+1);
        }
    }
    for(int i=1;i<=n;i++)
        ans=max(ans,f[n][i]);
    printf("%d\n",ans);
    return 0;
}