记录编号	79647	评测结果	AAAAAAAAAA
题目名称	交错匹配	最终得分	100
用户昵称	digital-T	是否通过	通过
代码语言	C++	运行时间	0.012 s
提交时间	2013-11-06 08:18:41	内存使用	1.27 MiB

#include<fstream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
ifstream fi("crossa.in");
ofstream fo("crossa.out");
int N,M,UP[500],DOWN[500],f[500][500];

int main()
{
	fi>>N>>M;
	for(int i=1;i<=N;i++)fi>>UP[i];
	for(int j=1;j<=M;j++)fi>>DOWN[j];
	int UPlast,DOWNlast;
	memset(f,0,sizeof(f));
	for(int i=1;i<=N;i++)
		for(int j=1;j<=M;j++)
		{
			f[i][j]=max(f[i][j-1],f[i-1][j]);
			if(UP[i]==DOWN[j])continue;
			UPlast=i;
			while(UPlast>0&&UP[UPlast]!=DOWN[j])UPlast--;
			DOWNlast=j;
			while(DOWNlast>0&&DOWN[DOWNlast]!=UP[i])DOWNlast--;
			if(UPlast && DOWNlast)
				f[i][j]=max(f[i][j],f[UPlast-1][DOWNlast-1]+2);
		}
	fo<<f[N][M]<<endl;
	return 0;
}