记录编号	35943	评测结果	AAAAAAAAAA
题目名称	田忌赛马	最终得分	100
用户昵称	QhelDIV	是否通过	通过
代码语言	C++	运行时间	1.397 s
提交时间	2012-03-06 20:48:28	内存使用	95.75 MiB

#include <fstream>
#include <cstdlib>
using namespace std;
ifstream fin("horsea.in");
ofstream fout("horsea.out");
short int f[5001][5001],v[5001][5001];
int H1[10000],H2[10000],n;
int Cmp(const void *p1,const void *p2)
{
	return *(int *)p2 - *(int *)p1;
}
void Initialize()
{
int i,j;
	fin>>n;
	for(i=1;i<=n;i++)
		fin>>H1[i];
	for(i=1;i<=n;i++)
		fin>>H2[i];
	qsort(H1+1,n,sizeof(int),Cmp);
	qsort(H2+1,n,sizeof(int),Cmp);
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
			if(H1[j]>H2[i])
				v[i][j]=-1;
			else
				if(H1[j]<H2[i])
					v[i][j]=1;
				else
					v[i][j]=0;
	}
	for(i=1;i<=n;i++)
	{
		f[i][0]=f[i-1][0]+v[n-i+1][i];
		f[i][i]=f[i-1][i-1]+v[i][i];
	}
}

void dp()
{
int i,j;	
	for(i=1;i<=n;i++)
		for(j=1;j<=i;j++)
			if(i!=j)
			{
				if(f[i-1][j-1]+v[j][i] > f[i-1][j]+v[n-(i-j)+1][i])
					f[i][j]=f[i-1][j-1]+v[j][i];
				else
					f[i][j]=f[i-1][j]+v[n-(i-j)+1][i];
			}
}

void Op()
{
int i,Max=-10000;
	for(i=1;i<=n;i++)
		if(Max<f[n][i])
			Max=f[n][i];
	fout<<Max<<endl;
}

int main()
{
	Initialize();
	
	dp();
	
	Op();
	
	fin.close();
	fout.close();
	return 0;
}