AcWing 272. 最长公共上升子序列
原题链接
中等
作者:
jiashihong
,
2019-08-09 10:24:50
,
所有人可见
,
阅读 752
#include<bits/stdc++.h>
using namespace std;
#define LL long long
int n;
int F[3010];
int a[3010];
int b[3010];
void LCIS(){
memset(F,0,sizeof(F));
for(int i=1;i<=n;i++){
LL maxn = 0;
for(int j=1;j<=n;j++){
if(a[i] > b[j] && maxn < F[j]) maxn = F[j];
if(a[i] == b[j]) F[j] = maxn+1;
}
}
LL maxn = 0;
for(int i = 1;i<=n;i++){
if(maxn < F[i]) maxn = F[i];
}
printf("%lld\n",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];
}
LCIS();
return 0;
}