Link_Cut_Y @ 2021-08-16 13:38:12
#include<bits/stdc++.h>
#define int long long
#define reint register int
#define forr(i,a,b) for(reint i=(a);i<=(b);i++)
using namespace std;
const int N=2010;
int a[N];
int b[N];
int f[N][N];
bool digit(char x)
{
return (x>='0' && x<='9');
}
inline int read()
{
int x=0;
int f=1;
char ch=getchar();
while(!digit(ch))
{
if(ch=='-')
{
f=-1;
}
ch=getchar();
}
while(digit(ch))
{
x=(x<<1)+(x<<3)+ch-'0';
ch=getchar();
}
return x*f;
}
inline void write(int x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)
write(x/10);
putchar(x%10+'0');
return;
}
signed main()
{
int n;
int sum=0;
n=read();
for(int i=1;i<=n;i++)
{
a[i]=read();
}
for(int j=1;j<=n;j++)
{
b[j]=read();
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
f[i][j]=max(f[i-1][j],f[i][j-1]);
if(a[i]==b[j])
{
f[i][j]=max(f[i][j],f[i-1][j-1]+1);
}
}
}
write(f[n][n]);
}
另外,有没有优化做法提供一下谢谢
by _l_l_l_l_l_ @ 2021-08-16 14:00:19
@maodan12345 开到
by Link_Cut_Y @ 2021-08-16 14:00:38
@十里 开滚动数组应该可以
by Link_Cut_Y @ 2021-08-16 14:00:51
我试一试吧
by Link_Cut_Y @ 2021-08-16 14:01:43
@WenZKbb dalao有什么优化方法吗?
by _l_l_l_l_l_ @ 2021-08-16 14:04:29
@maodan12345 可以看一眼 https://www.luogu.com.cn/blog/WenZKbb/LCS-Onlogn-note
by Link_Cut_Y @ 2021-08-16 14:39:15
感谢dalao我懂了