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 Link_Cut_Y @ 2021-08-16 13:47:23
@huyifei323
by huyifei323 @ 2021-08-16 13:50:59
@maodan12345 建议直接用long long或#define ll long long
,不要#define int long long
,#define int long long
会导致int main()
时变成long long main()
从而导致RE
by Link_Cut_Y @ 2021-08-16 13:56:26
@huyifei323 但是我用signed main了啊
by Link_Cut_Y @ 2021-08-16 13:56:56
楼上dalao说二分法才能过
by Sliarae @ 2021-08-16 13:57:13
@huyifei323 RE是应为数组开小了吧
by _l_l_l_l_l_ @ 2021-08-16 13:58:50
@maodan12345 二分?我记得是转换成LIS
https://www.luogu.com.cn/blog/WenZKbb/LCS-Onlogn-note
by Link_Cut_Y @ 2021-08-16 13:58:52
@十里 应该开到1e5
by _l_l_l_l_l_ @ 2021-08-16 13:59:34
@maodan12345 这题
by Sliarae @ 2021-08-16 13:59:51
@maodan12345 这题数据量有
by Link_Cut_Y @ 2021-08-16 14:00:05
lower_bound 就是二分吧