#include<iostream> #include<algorithm> #include<cstring> using namespace std ; const int N = 3010 ; int f[N][N] ;//前i个数和前j个数并且以b[j] 结尾的最长公告上升子序列 int n ; int a[N] ; int b[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 S = 0 ; for(int j = 1 ; j <= n ;j ++){ f[i][j] = f[i-1][j] ; if(b[j-1] < a[i]) S = max(S , f[i-1][j-1] + 1) ;//因为我们更新的话只有a[i] == b[j] 的情况也就是说我们的a[i]是一直不变的，我们只需要判断新加入的b[j-1]能不能成为之前的最长公共上升子序列 if(a[i]==b[j]) f[i][j] = max(S,f[i][j]) ; } } int res = 0 ; for(int i = 1 ; i <= n ; i ++) res = max(res,f[n][i]) ; cout << res << endl ; }
#include<iostream> #include<cstring> #include<algorithm> using namespace std ; const int N = 3010 ; int f[N][N] ; int a[N],b[N] ; int main(){ int n ;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 s = 1 ;//s记录的是以a[i]结尾的最长上升子序列的最大长度 for(int j = 1 ; j <= n ; j ++){ f[i][j] = f[i-1][j] ; if(b[j] == a[i])f[i][j] = max(f[i][j], s);//找到和这层循环的a[i]相等的b[j]，就用s取更新他 if(b[j] < a[i]) s = max(s,f[i][j] + 1) ; } } int res = f[n][1] ; for(int i = 1 ; i <= n ;i ++){ res = max(res,f[n][i]) ; } cout << res << endl ; }
