记录编号	36048	评测结果	AAAAAAAAAA
题目名称	田忌赛马	最终得分	100
用户昵称	Czb。	是否通过	通过
代码语言	C++	运行时间	0.584 s
提交时间	2012-03-08 16:16:15	内存使用	47.98 MiB

#include<stdio.h>
#include<stdlib.h>
 
short n,ans,a[5001],b[5001],f[5001][5001];
 
short max(short a,short b)
{
	return a>b?a:b;
}
 
short s(short a,short b)
{
	if(a>b)
		return -1;
	else if(a<b)
		return 1;
	else
		return 0;
}
 
int cmp(const void *a,const void *b)
{
	return *(short *)a-*(short *)b;
}
 
int main()
{
	freopen("horsea.in","r",stdin);
	freopen("horsea.out","w",stdout);
	int i,j;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	for(i=1;i<=n;i++)
	{
		scanf("%d",&b[i]);
	}
	qsort(a+1,n,2,cmp);
	qsort(b+1,n,2,cmp);
	for(i=1;i<=n;i++)
	{
		f[i][0]=f[i-1][0]+s(a[n-i+1],b[i]);
		for(j=1;j<i;j++)
		{
			f[i][j]=max(f[i-1][j]+s(a[n-i+1],b[i-j]),f[i-1][j-1]+s(a[n-i+1],b[n-j+1]));
		}
		f[i][i]=f[i-1][i-1]+s(a[n-i+1],b[n-i+1]);
	}
	ans=-10000;
	for(i=0;i<=n;i++)
	{
		if(f[n][i]>ans)
			ans=f[n][i];
	}
	printf("%d\n",ans);
	return 0;
}