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

#include<cstdio>
#include<iostream>
#include<cstdlib>

using namespace std;

int cmp(const void *a,const void *b)
{
     return *(int *)b-*(int *)a;
} 

int Tianji[5005],king[5005];
int money[5005][5005];
int profit(int x,int y);
int max(int x,int y);
int main()
{
	freopen("horsea.in","r",stdin);
	freopen("horsea.out","w",stdout);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>king[i];
	}
	for(int i=1;i<=n;i++)
	{
		cin>>Tianji[i];
	}
	qsort(king+1,n,sizeof(king[0]),cmp);
	qsort(Tianji+1,n,sizeof(Tianji[0]),cmp);
	for(int i=1;i<=n;i++)
	{
		money[i][0]=money[i-1][0]+profit(n-i+1,i);
		money[i][i]=money[i-1][i-1]+profit(i,i);
		for(int j=1;j<i;j++)
		{
			money[i][j]=max((money[i-1][j]+profit(n-i+j+1,i)),(money[i-1][j-1]+profit(j,i)));
		}
	}
	int ans=-999999;
	for(int i=0;i<=n;i++)
	{
		if(money[n][i]>ans)
		{
			ans=money[n][i];
		}
	}
	cout<<ans<<endl;
	return 0;
}
int profit(int x,int y)
{
	if(Tianji[x]>king[y])
	{
		return 1;
	}
	if(Tianji[x]<king[y])
	{
		return -1;
	}
	else
	{
		return 0;
	}
}
int max(int x,int y)
{
	if(x>y)
		return x;
	else
		return y;
}