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 Leonid @ 2021-08-16 13:39:21
有看数据范围吗……
by Link_Cut_Y @ 2021-08-16 13:40:15
原来用STL lower_bound 水了过去,现在想看看DP怎么写qwq
by Link_Cut_Y @ 2021-08-16 13:40:39
1e5!!!
by Link_Cut_Y @ 2021-08-16 13:41:02
我哭了
by JRzyh @ 2021-08-16 13:42:25
@maodan12345 那不是水过去
by JRzyh @ 2021-08-16 13:42:56
二分法是这种问题的正解
by huyifei323 @ 2021-08-16 13:45:10
@maodan12345 要用long long
by Link_Cut_Y @ 2021-08-16 13:45:22
???蒟蒻表示很惊讶
by Link_Cut_Y @ 2021-08-16 13:45:49
好的谢谢dalao
by Link_Cut_Y @ 2021-08-16 13:46:52
不对啊,我已经define int long long了啊