记录编号	35984	评测结果	AAAAAAAAAA
题目名称	田忌赛马	最终得分	100
用户昵称	Launcher	是否通过	通过
代码语言	C++	运行时间	1.321 s
提交时间	2012-03-07 13:48:52	内存使用	95.73 MiB

#include<fstream>
using namespace std;
ifstream fin("horsea.in");
ofstream fout("horsea.out");
short a[5002]={0},b[5002]={0},w[5002][5002]={0},f[5002][5002]={0};
void sort(int l,int r)
{
	int i,j;
	int  x,y;
	i=l;
	j=r;
	x=a[(l+r)/2];
	do 
	{
	    while (a[i]>x) i++;
		while (a[j]<x) j--;
		if (i<=j)
		{
			y=a[i];
			a[i]=a[j];
			a[j]=y;
			i++;
			j--;
		}
	}
	while (i<=j);
	if (l<j) sort(l,j);
	if (i<r) sort(i,r);
}
int Max(int x,int y)
{
	int z;
	if (x>y)
		return x;
	else
		return y;
}
void sqort(int l,int r)
{
	int i,j;
	int  x,y;
	i=l;
	j=r;
	x=b[(l+r)/2];
	do 
	{
	    while (b[i]>x) i++;
		while (b[j]<x) j--;
		if (i<=j)
		{
			y=b[i];
			b[i]=b[j];
			b[j]=y;
			i++;
			j--;
		}
	}
	while (i<=j);
	if (l<j) sqort(l,j);
	if (i<r) sqort(i,r);
}


int main()
{
	int i,j,k=0,l=0,x,y;
	int n=0,money=0;
	fin>>n;
	x=n;
	money=-5002;
	y=n;
    for (i=1;i<=n;i++)
		fin>>a[i];
	for (i=1;i<=n;i++)
		fin>>b[i];
	sort(1,n);
	sqort(1,n);

	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
		{
			if (a[j]>b[i]) 
				w[j][i]=-1;
			if (a[j]<b[i]) 
				w[j][i]=1;
			if (a[j]==b[i]) 
				w[j][i]=0;
			
		}

	f[0][0]=0;	

	for (i=1;i<=n;i++)
	{
		f[i][0]=f[i-1][0]+w[i][n-i+1];
	//	f[0][i]=f[0][i-1]+w[n-i+1][i];
		f[i][i]=f[i-1][i-1]+w[i][i];
	}
	for (i=1;i<=n;i++)
		for (j=1;j<i;j++)
		{
			f[i][j]=Max(f[i-1][j-1]+w[i][j],f[i-1][j]+w[i][n-(i-j)+1]);
		}
//	for (i=1;i<=n;i++)
//	{
//		for (j=1;j<=n;j++)
//			fout<<w[i][j]<<' ';
//	    fout<<endl;
//	}

	for (j=0;j<=n;j++)
	{
		
	    if (money<f[n][j])
			money=f[n][j];
	}
	
	fout<<money<<endl;
	fin.close();
	fout.close();
	return 0;
}