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

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
int n;
int q[5100],w[5100];
int answer=-88888;
int cmp ( const void *a , const void *b )
{
	return *(int *)b - *(int *)a;
}
short int f[5001][5001];
int main()
{
	freopen ("horsea.in","r",stdin);
	freopen ("horsea.out","w",stdout);
	cin>>n;
	q[0]=w[0]=600;
	for (int i=1;i<=n;i++)
	{
		cin>>q[i];
	}
	for (int i=1;i<=n;i++)
	{
		cin>>w[i];
	}
	f[0][0]=0;
	qsort(q,n+1,sizeof(q[0]),cmp);
	qsort(w,n+1,sizeof(w[0]),cmp);
	for (int i=1;i<=n;i++)
	{
		int c,a;
		if (q[i]>w[n-i+1])
			c=-1;
		if (q[i]<w[n-i+1])
			c=1;
		if (q[i]==w[n-i+1])
			c=0;
		f[i][0]=f[i-1][0]+c;
		if (q[i]>w[i])
			a=-1;
		if (q[i]<w[i])
			a=1;
		if (q[i]==w[i])
			a=0;
		f[i][i]=f[i-1][i-1]+a;
	}
	for (int i=2;i<=n;i++)
	{
		for (int j=1;j<=n;j++)
		{
			if (j>=i)
				continue;
			int a,b;
			if (q[i]>w[j])
				a=-1;
			if (q[i]<w[j])
				a=1;
			if (q[i]==w[j])
				a=0;
			if (q[i]>w[n-(i-j)+1])
				b=-1;
			if (q[i]<w[n-(i-j)+1])
				b=1;
			if (q[i]==w[n-(i-j)+1])
				b=0;
			f[i][j]=max(f[i-1][j-1]+a,f[i-1][j]+b);
		}
	}
	for (int i=1;i<=n;i++)
	{
		if (f[n][i]>answer)
		{
			answer=f[n][i];
		}
	}
	cout<<answer;
	return 0;
}