记录编号	35965	评测结果	AAAAAAAAAA
题目名称	田忌赛马	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	1.619 s
提交时间	2012-03-06 21:45:21	内存使用	95.74 MiB

#include <cstdio>
#include <cstdlib>
using namespace std;

int king[5002]={0},tian[5002]={0};
short map[5002][5002]={0},f[5002][5002]={0};

void swap(int &x,int &y)
{
	int temp;
	temp=x;
	x=y;
	y=temp;
}

void qqsort(int* num,int l,int r)
{
	int ll=l,rr=r,temp;
	temp=num[rand()%(r-l+1)+l];
	while (ll<=rr)
	{
		while (num[ll]>temp)
			ll++;
		while (temp>num[rr])
			rr--;
		if (ll<=rr)
		{
			swap(num[ll],num[rr]);
			ll++;
			rr--;
		}
	}
	if (l<rr)
		qqsort(num,l,rr);
	if (ll<r)
		qqsort(num,ll,r);
}

int main(void)
{
	freopen("horsea.in","r",stdin);
	freopen("horsea.out","w",stdout);
	int i,j,n,temp;
	scanf("%d",&n);
	for (i=1;i<=n;i++)
		scanf("%d",&king[i]);
	for (i=1;i<=n;i++)
		scanf("%d",&tian[i]);
	qqsort(king,1,n);
	qqsort(tian,1,n);
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
			if (king[i]>tian[j])
				map[i][j]=-1;
			else if (king[i]<tian[j])
				map[i][j]=1;
	for (i=1;i<=n;i++)
		f[i][0]=f[i-1][0]+map[i][n-i+1];
	for (i=1;i<=n;i++)
		f[i][i]=f[i-1][i-1]+map[i][i];
	for (j=1;j<=n;j++)
		for (i=j+1;i<=n;i++)
		{
			f[i][j]=f[i-1][j]+map[i][n-(i-j)+1];
			temp=f[i-1][j-1]+map[i][j];
			if (f[i][j]<temp)
				f[i][j]=temp;
		}
	temp=-100000;
	for (i=0;i<=n;i++)
		if (temp<f[n][i])
			temp=f[n][i];
	printf("%d\n",temp);
	return(0);
}