AcWing 272. 最长公共上升子序列
原题链接
中等
作者:
upp1
,
2023-05-08 17:08:41
,
所有人可见
,
阅读 192
未简化(超时)
#include <bits/stdc++.h>
using namespace std;
const int N=3010;
int n;
int a[N],b[N];
int f[N][N];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int j=1;j<=n;j++)
cin>>b[j];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
f[i][j]=f[i-1][j];//不包含a[i]
if(a[i]==b[j])
{
int max1=1;
for(int k=1;k<j;k++)
{
if(b[k]<b[j])
max1=max(max1,f[i-1][k]+1);
f[i][j]=max(max1,f[i][j]);
}
}
}
}
int res=0;
for(int i=1;i<=n;i++)
res=max(res,f[n][i]);
cout<<res;
return 0;
}
简化
#include <bits/stdc++.h>
using namespace std;
const int N=3010;
int n;
int a[N],b[N];
int f[N][N];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int j=1;j<=n;j++)
cin>>b[j];
for(int i=1;i<=n;i++)
{
int max1=1;
for(int j=1;j<=n;j++)
{
f[i][j]=f[i-1][j];
if(a[i]==b[j])//更新f[i,j]的条件
f[i][j]=max(max1,f[i][j]);
if(b[j]<a[i])
max1=max(max1,f[i-1][j]+1);
}
}
int res=0;
for(int i=1;i<=n;i++)
res=max(res,f[n][i]);
cout<<res;
return 0;
}