本文共 1259 字，大约阅读时间需要 4 分钟。

题目大意

给定两个序列，求他们的最长公共上升子序列

样例

输入样例：42 2 1 32 1 2 3输出样例：2

思路

1. 当Ai != Bj 时， F[i, j] = F [i - 1, j]
2. 当Ai = Bj 时， F[i, j] = 前面最长上升公共子序列 + 1

这样用代码表示出来就是

for(int i = 1; i <= n; i++)        for(int j = 1; j <= n; j++)       		 if(a[i] == b[j])            	for(int k = 0; k < j; k++){                   	if(b[k] < a[i])                     	f[i][j] = max(f[i][j], f[i - 1][k] + 1);             }          else f[i][j] = f[i - 1][j];

但是数据范围是3000， O（n ^ 3）时间复杂度显然不行

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;const int N = 3010;int a[N], b[N], f[N][N];int n;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 val = 0;        //if(b[0] < a[i]) val = f[i - 1][0]        for (int j = 1; j <= n; j ++ ){                if(a[i] == b[j]) f[i][j] = val + 1;            else f[i][j] = f[i - 1][j];            if(b[j] < a[i]) val = max(val, f[i - 1][j]);        }    }    int ans = 0;    for(int i = 1; i <= n; i++) ans = max(ans , f[n][i]);    cout << ans << endl;    return 0;}