记录编号	532251	评测结果	AAWWAWEEEE
题目名称	田忌赛马	最终得分	30
用户昵称	欧鹰123	是否通过	未通过
代码语言	C++	运行时间	0.913 s
提交时间	2019-05-25 20:19:11	内存使用	44.25 MiB

#include<bits/stdc++.h>
using namespace std;
int n,tian[2002],wang[2002],f[2002][2002],g[2002][2002],ans;
bool cmp(int a,int b)
{
	return a>b;
}
int main()
{
	freopen("horsea.in","r",stdin);
	freopen("horsea.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>wang[i];
	for(int i=1;i<=n;i++)cin>>tian[i];
	sort(wang+1,wang+1+n,cmp);
	sort(tian+1,tian+1+n,cmp);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(tian[i]>wang[j])f[i][j]=1;
			else if(tian[i]==wang[j])f[i][j]=0;
			else f[i][j]=-1;
			g[i][j]=21475986;
		}
	}
	//设g[i][j]表示齐王
	//按从强到弱的顺序出马和田忌进行了i场比赛之后，
	//从""头""取了j匹较强的马，从""尾""取了i-j匹较弱的马，
	//所能获得的最大盈利。
	for(int i=1;i<=n;i++)
	{
		g[i][0]=g[i-1][0]+f[n-i+1][i];
		g[i][i]=g[i-1][i-1]+f[i][i];
		for(int j=1;j<i;j++)g[i][j]=max(g[i-1][j]+f[n-i+j+1][i],g[i-1][j-1]+f[j][i]);
	}
	for(int i=1;i<=n;i++)ans=max(ans,g[n][i]);
    cout<<ans;
	return 0;
}