记录编号	28189	评测结果	AAAAAAAAAA
题目名称	交错匹配	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.016 s
提交时间	2011-10-11 21:26:17	内存使用	0.65 MiB

#include <cstdio>
using namespace std;

int main(void)
{
	freopen("crossa.in","r",stdin);
	freopen("crossa.out","w",stdout);
	int i,j,i2,j2,n,m,up[202]={0},down[202]={0},posup[202][202]={{0}},posdown[202][202]={{0}},f[202][202]={{0}};
	scanf("%d %d",&n,&m);
	for (i=1;i<=n;i++)
		scanf("%d",&up[i]);
	for (i=1;i<=m;i++)
		scanf("%d",&down[i]);
	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++)
			if (up[i]!=down[j])
			{
				for (i2=i-1;i2>=1;i2--)
					if (down[j]==up[i2])
					{
						posup[i][j]=i2;
						break;
					}
//				if (i2==0)
//					posup[i][j]=-1;
				for (j2=j-1;j2>=1;j2--)
					if (down[j2]==up[i])
					{
						posdown[i][j]=j2;
						break;
					}
//				if (j2==0)
//					posdown[i][j]=-1;
			}
//			else
//			{
//				posup[i][j]=-1;
//				posdown[i][j]=-1;
//			}
	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++)
		{
			if (j-1>=0&&f[i][j-1]>f[i][j])
				f[i][j]=f[i][j-1];
			if (i-1>=0&&f[i-1][j]>f[i][j])
				f[i][j]=f[i-1][j];
			if (posup[i][j]-1>=0&&posdown[i][j]-1>=0&&f[posup[i][j]-1][posdown[i][j]-1]+2>f[i][j])
				f[i][j]=f[posup[i][j]-1][posdown[i][j]-1]+2;
		}
	printf("%d\n",f[n][m]);
	fclose(stdin);
	fclose(stdout);
	return(0);
}