比赛 20110928 评测结果 AAAAWAAAAA
题目名称 交错匹配 最终得分 90
用户昵称 Citron酱 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-09-28 20:54:13
显示代码纯文本
#include <fstream>

#define I_F "crossa.in"
#define O_F "crossa.out"

const int MAXn=200;

int l[2];
int s[2][MAXn];
int p[2][MAXn][MAXn];
int ans;

void Input();
void Predo();
int Max(const int, const int);
void Dynap();
void Output();

int main()
{
	Input();
	Predo();
	Dynap();
	Output();
	return 0;
}

void Input()
{
	std::ifstream fin(I_F);
	fin>>l[0]>>l[1];
	for (short i=0; i<2; i++)
		for (int j=0; j<l[i]; fin>>s[i][j++]);
	fin.close();
}

void Predo()
{
	for (short i=0; i<2; i++)
		for (int j=0; j<l[i]; j++)
		{
			p[i][j][0]=(s[i][j]==s[1-i][0])?0:-1;
			for (int k=1; k<l[1-i]; k++)
				p[i][j][k]=(s[i][j]==s[1-i][k])?k:p[i][j][k-1];
		}
}

int Max(const int a, const int b)
{
	return (a>b)?a:b;
}

void Dynap()
{
	int f[MAXn][MAXn]={0};
	for (int i=1; i<l[0]; i++)
		for (int j=1; j<l[1]; j++)
			if (p[0][i][j]>=0 && p[1][j][i]>=0 && (!(p[0][i][j]==j && p[1][j][i]==i)))
				f[i][j]=Max(f[i-1][j],Max(f[i][j-1],((p[0][i][j]*p[1][j][i]>0)?f[p[1][j][i]-1][p[0][i][j]-1]:0)+1));
			else
				f[i][j]=Max(f[i][j-1],f[i-1][j]);
	ans=f[l[0]-1][l[1]-1]*2;
}

void Output()
{
	std::ofstream fout(O_F);
	fout<<ans<<std::endl;
	fout.close();
}