只有我自己能看懂…各位大佬换一个吧…写的太差了

优化前的代码：

C++ 代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3010;
int n;
int a[maxn], b[maxn], f[maxn][maxn]; //f[i][j] 代表b序列第j个与a序列第i个字符之前的最长公共上升子序列

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 ++) //从头开始循环
    {
//      int maxi = 1;
        for(int j = 1; j <= n; j ++)
        {
            f[i][j] = f[i-1][j]; // 状态划分，分两类，第二类就是a[i] != a[j]                           因为取两个状态的max值，所以我们可以先等于一类，再与另一类比较
            if(a[i] == b[j]) //当相等的时候， 则为状态划分的第二类
            {
            //  f[i][j] = max(f[i][j], maxi);
                f[i][j] = max(f[i][j], 1);  //由于可能a[i]之前没有与b相等的 故为1
                for(int k = 1; k < j; k ++) //循环状态与a[i]相等那一类的前多种状态..好像有点啰嗦
                {
                    if(b[k] < a[i]) // 这里的循环就是找最长上升子序列的循环
                    {
                        f[i][j] = max(f[i][j], f[i][k] + 1);
                    }
                }
            }
//          if(b[j] < a[i])
//          {
//              maxi = max(maxi, f[i][j] + 1);
//          }
        }
    }

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

    cout << res << endl;

    return 0;
}

优化后的On2 的代码

C++ 代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3010;
int n;
int a[maxn], b[maxn], f[maxn][maxn];

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 ++)
    {
        int maxi = 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], maxi);
//              f[i][j] = max(f[i][j], 1);
//              for(int k = 1; k < j; k ++)
//              {
//                  if(b[k] < a[i])         
//                  {
//                      f[i][j] = max(f[i][j], f[i][k] + 1);
//                  }
//              }
            }
            if(b[j] < a[i])
            {
                maxi = max(maxi, f[i][j] + 1);
            }
        }
    }

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

    cout << res << endl;

    return 0;
}