NKOJ 2409 田忌赛马 （DP）

发表于 |
字数统计: 551字 | 阅读时长 ≈ 2min

P2409【9月月赛T2】田忌赛马

问题描述

中国古代的历史故事“田忌赛马”是为大家所熟知的。话说齐王和田忌又要赛马了，他们各派出N匹马，每场比赛，输的一方将要给赢的一方200两黄金，如果是平局的话，双方都不必拿出钱。
现在每匹马的速度值是固定而且已知的，而齐王出马也不管田忌的出马顺序。请问田忌该如何安排自己的马去对抗齐王的马，才能赢取最多的钱？

输入格式

第1行为一个正整数n，表示双方马的数量。
第2行有N个整数表示田忌的马的速度。
第3行的N个整数为齐王的马的速度。

输出格式

仅有1行，田忌赛马可能赢得的最多的钱，结果有可能为负。

样例输入

3
92 83 71
95 87 74

样例输出

200

提示

0<=n<=2000 马的速度<=10000

此题可以借鉴田忌赛马的方式，将田忌和齐王的马从大到小排序，然后我们依次讨论用那匹马去对齐王的队首马，显然要么用队首的马，要么用队尾的马，因此可以令$F[i][j]$表示用第i匹马到第j匹马去对齐王剩下的$j-i+1$匹马的最大收益，然后转移即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
bool cmp(int a,int b)
{return a>b;}
int n,A[2005],B[2005],F[2005][2005];
int G(int a,int b)
{
	if(A[a]>B[b])return 200;
	if(A[a]==B[b])return 0;
	if(A[a]<B[b])return -200;
}
int dp(int x,int y)
{
	if(x==y)return F[x][y]=G(x,n);
	if(F[x][y]!=F[0][0])return F[x][y];
	return F[x][y]=max(dp(x+1,y)+G(x,n+x-y),dp(x,y-1)+G(y,n+x-y));
}
int main()
{
	int i;
	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%d",&A[i]);
	for(i=1;i<=n;i++)scanf("%d",&B[i]);
	sort(A+1,A+n+1,cmp);
	sort(B+1,B+n+1,cmp);
	memset(F,-10,sizeof(F));
	printf("%d\n",dp(1,n));
}