1 条题解
-
0
刷题去 LV 9 MOD @ 8 年前
- 1
信息
- 难度
- 10
- 分类
- (无)
- 标签
- (无)
- 递交数
- 2
- 已通过
- 0
- 通过率
- 0%
- 上传者
#include<cstdio>
#include<algorithm>
using namespace std;
int up[203],down[203],f[203][203],ip[203][203],jp[203][203];
int n,m;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&up[i]);
for(int i=1;i<=m;i++)
scanf("%d",&down[i]);
for(int i=1;i<=n;i++){
for(int j=2;j<=m;j++){
if(down[j-1]==up[i]) jp[i][j]=j-1;
else jp[i][j]=jp[i][j-1];
}
}
for(int i=2;i<=n;i++){
for(int j=1;j<=n;j++){
if(up[i-1]==down[j]) ip[i][j]=i-1;
else ip[i][j]=ip[i-1][j];
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
f[i][j]=max(f[i-1][j],f[i][j-1]);
f[i][j]=max(f[i-1][j-1],f[i][j]);
if(up[i]!=down[j])
{ int x=ip[i][j],y=jp[i][j];
if(x!=0&&y!=0)
f[i][j]=max(f[i][j],f[x-1][y-1]+2);
}
}
printf("%d",f[n][m]);
return 0;
}