$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

思路：

• $1. 状态表示$
  $集合：所有\ a_{1\sim i}\ 和\ b_{1\sim j}\ 中以\ b_j\ 为结尾的公共上升子序列$
  $属性：\max$

• $2. 状态转移$
  $不包含\ a_i：f[i][j]=f[i-1][j]$
  $包含\ a_i\ (a_i=b_j)：f[i][j]=\max \{ f[i-1][k]+1\}(k<j,b_k<b_j)$

• $3. 优化$
  $maxv\ 是满足\ a_i>b_k\ 的\ f[i-1][k]+1\ 的前缀最大值$

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 3010;

int n;
int a[N],b[N];
int f[N][N]; //所有 a[1 ~ i] 和 b[1 ~ j] 中以 b[j] 为结尾的最长公共上升子序列

int main()
{
    cin>>n;

    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];

    // 三重循环
    // for(int i=1;i<=n;i++)
    //     for(int j=1;j<=n;j++)
    //     {
    //         f[i][j]=f[i-1][j];
    //         if(a[i]==b[j])
    //         {
    //             int maxv=1;
    //             for(int k=1;k<j;k++)
    //                 if(b[k]<b[j])
    //                     maxv=max(maxv,f[i-1][k]+1);

    //             f[i][j]=max(f[i][j],maxv);
    //         }
    //     }

    // 优化后
    for(int i=1;i<=n;i++)
    {
        int maxv=1;
        for(int j=1;j<=n;j++)
        {
            f[i][j]=f[i-1][j];
            if(a[i]>b[j]) maxv=max(maxv,f[i-1][j]+1); //前缀最大值
            if(a[i]==b[j]) f[i][j]=max(f[i][j],maxv);
        }
    }

    int res=0;
    for(int i=1;i<=n;i++) res=max(res,f[n][i]);

    cout<<res<<endl;

    return 0;
}