AcWing 272. 最长公共上升子序列
原题链接
中等
作者:
hopeforyou
,
2023-11-20 21:42:02
,
所有人可见
,
阅读 41
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std ;
const int N = 3010 ;
int n ;
int num1[N] , num2[N] ;
int dp[N][N] ;
int main ()
{
scanf ("%d" , &n) ;
for (int i = 1 ; i <= n ; i++) scanf ("%d" , &num1[i]) ;
for (int i = 1 ; i <= n ; i++) scanf ("%d" , &num2[i]) ;
for (int i = 1; i <= n; i ++ ){
int maxv = 1;
for (int j = 1; j <= n; j ++ ){
dp[i][j] = dp[i - 1][j];
if (num1[i] == num2[j]) dp[i][j] = max(dp[i][j], maxv);
if (num2[j] < num1[i]) maxv = max(maxv, dp[i - 1][j] + 1);
}
}
int res = 0 ;
for (int i = 1 ; i <= n ; i++) res = max (res , dp[n][i]) ;
printf ("%d" , res) ;
return 0 ;
}