记录编号	185080	评测结果	AAAAAAAAAA
题目名称	田忌赛马	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.339 s
提交时间	2015-09-04 15:33:36	内存使用	96.10 MiB

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
const int INF=0x7fffffff;
int N,q[5010],t[5010];
int f[5010][5010]={0};
int ans=-INF;
bool cmp(int a,int b)
{
	return a>b;
}
int g(int j,int i)
{
	if(t[j]<q[i]) return -1;
	if(t[j]==q[i]) return 0;
	if(t[j]>q[i]) return 1;
}
void DP()
{
	sort(q+1,q+N+1,cmp);
	sort(t+1,t+N+1,cmp);
	for(int i=1;i<=N;i++)
		for(int j=0;j<=i;j++)
		{
			f[i][j]=-INF;
			if(j!=i) f[i][j]=max(f[i-1][j]+g(N-(i-j)+1,i),f[i][j]);
			if(j!=0) f[i][j]=max(f[i-1][j-1]+g(j,i),f[i][j]);
			if(i==N) ans=max(ans,f[i][j]);
			//cout<<i<<" "<<j<<" "<<f[i][j]<<endl;
		}
	printf("%d",ans);
}
int main()
{
	freopen("horsea.in","r",stdin);
	freopen("horsea.out","w",stdout);
	scanf("%d",&N);
	for(int i=1;i<=N;i++)
		scanf("%d",&q[i]);
	for(int i=1;i<=N;i++)
		scanf("%d",&t[i]);
	DP();
	return 0;
}