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

#include <cstdlib>
#include <cstdio>
#define Circle for(int i=1;i<=N;i++)
using namespace std;
const int MAXN=5001;
typedef short int sint;
sint King[MAXN];
sint Tian[MAXN];
sint Win[MAXN][MAXN];
sint F[MAXN][MAXN];
int N;

int cmp(const void *a,const void *b)
{
	sint *c=(sint *)a; 
	sint *d=(sint *)b;
	return *d>*c?1:-1;
}

void init()
{
	scanf("%d\n",&N);
	Circle scanf("%d",&King[i]);
	Circle scanf("%d",&Tian[i]);
	qsort(King+1,N,sizeof(sint),cmp);
	qsort(Tian+1,N,sizeof(sint),cmp);
	/*Circle printf("%d ",King[i]);
	printf("\n");
	Circle printf("%d ",Tian[i]);*/
	for(int i=1;i<=N;i++)
	{
		for(int j=1;j<=N;j++)
		{
			Win[i][j]=King[i]>Tian[j]?-1:1;
			if(King[i]==Tian[j]) Win[i][j]=0;
			/*printf("%d ",Win[i][j]);*/
		}
		/*printf("\n");*/
	}	
}

sint Max(sint a,sint b)
{
	return a>b?a:b;
}

void dp()
{
	F[0][0]=0;
	for(int i=1;i<=N;i++)
	{
		F[i][i]=F[i-1][i-1]+Win[i][i];
		F[i][0]=F[i-1][0]+Win[i][N-i+1];
	}
	for(int i=2;i<=N;i++)
	{
		for(int j=1;j<=N;j++)
		{
			if(j>=i) continue;
			F[i][j]=Max(F[i-1][j-1]+Win[i][j],F[i-1][j]+Win[i][N-i+j+1]);
		}
	}
	sint Ans=-10000;
	for(int i=0;i<=N;i++)
		Ans=Max(F[N][i],Ans);
	printf("%hd\n",Ans);
}

int main()
{
	freopen("horsea.in","r",stdin);
	freopen("horsea.out","w",stdout);
	init();
	dp();
	return 0;
}