记录编号	86911	评测结果	AAAAAAAAAA
题目名称	田忌赛马	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	1.269 s
提交时间	2014-01-28 21:26:21	内存使用	96.06 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iomanip>
#include<queue>
#include<deque>
#include<set>
using namespace std;
int N;
deque<int> T,K;//田忌和齐王
const int SIZEN=5010,INF=0x7fffffff;
int f[SIZEN][SIZEN]={0};//齐王按从强到弱赛i场,田忌从头取j匹,从尾取i-j匹的最大获利
int g(int i,int j){//田忌第i强的马和齐王第j强的马比赛的胜负(胜1负-1平0)
	if(T[i]>K[j]) return 1;
	if(T[i]==K[j]) return 0;
	return -1;
}
int main(){
	freopen("horsea.in","r",stdin);
	freopen("horsea.out","w",stdout);
	scanf("%d",&N);
	int temp;
	for(int i=0;i<N;i++) scanf("%d",&temp),K.push_back(temp);
	for(int i=0;i<N;i++) scanf("%d",&temp),T.push_back(temp);
	sort(K.begin(),K.end(),greater<int>());
	sort(T.begin(),T.end(),greater<int>());
	for(int i=0;i<=N;i++) for(int j=0;j<=N;j++) f[i][j]=-INF;
	f[0][0]=0;
	for(int i=1;i<=N;i++){
		for(int j=0;j<=i;j++){
			//在本场比赛中,齐王使用的是第i-1号马
			//田忌有两种选择:
			//1:使用第j-1号马,那么上一个状态就是f[i-1][j-1]
			//2:使用第n-(i-j)号马,那么上一个状态就是f[i-1][j]
			if(j) f[i][j]=max(f[i][j],f[i-1][j-1]+g(j-1,i-1));
			if(i>j) f[i][j]=max(f[i][j],f[i-1][j]+g(N-i+j,i-1));
		}
	}
	int ans=-INF;
	for(int i=0;i<=N;i++) ans=max(ans,f[N][i]);
	cout<<ans<<endl;
	return 0;
}