【描述】
中国古代的历史故事“田忌赛马”是为大家所熟知的。话说齐王和田忌又要赛马了，他们各派出N匹马，每场比赛，输的一方将要给赢的一方200两黄金，如果是平局的话，双方都不必拿出钱。现在每匹马的速度值是固定而且已知的，而齐王出马也不管田忌的出马顺序。请问田忌该如何安排自己的马去对抗齐王的马，才能赢取最多的钱？
【输入】
第一行为一个正整数n (n <= 2000) ，表示双方马的数量。
第二行有N个整数表示田忌的马的速度。
第三行的N个整数为齐王的马的速度。
【输出】
仅有一行，为田忌赛马可能赢得的最多的钱，结果有可能为负。
【样例输入】
3
92 83 71
95 87 74
【样例输出】
200
【分析】
如果齐王的马是按速度排序之后，从高到低被派出的话，田忌一定是将他马按速度排序之后，从两头取马去和齐王的马比赛。
n设f[i,j]表示齐王按从强到弱的顺序出马和田忌进行了i场比赛之后，从“头”取了j匹较强的马，从“尾”取了i-j匹较弱的马，所能够得到的最大盈利。
n状态转移方程如下：
nF[I,j]=max{f[i-1,j]+g[n-(i-j)+1,i],f[i-1,j-1]+g[j,i]}
n其中g[i,j]表示田忌的马和齐王的马分别按照由强到弱的顺序排序之后，田忌的第i匹马和齐王的第j匹马赛跑所能取得的盈利，胜为200，输为－200，平为0。
1: #include <stdio.h>
2: #include <limits.h>
3: #include <stdlib.h>
4: #define maxn 1010
5:
6: int a[maxn],b[maxn];
7: int g[maxn][maxn];
8: int f[2][maxn];
9: int n,er;
10: int ans;
11:
12: int cmp(const void*a,const void*b)
13: {
14: int c=*(int*)a,d=*(int*)b;
15: if (c<d) return 1;
16: if (c>d) return -1;
17: return 0;
18: }
19:
20: int main()
21: {
22: scanf("%d",&n);
23: for (int i=1;i<=n;++i) scanf("%d",&b[i]);
24: for (int i=1;i<=n;++i) scanf("%d",&a[i]);
25: a[0]=b[0]=INT_MAX;
26: qsort(a,n+1,sizeof(int),cmp);
27: qsort(b,n+1,sizeof(int),cmp);
28: for (int i=1;i<=n;++i)
29: for (int j=1;j<=n;++j)
30: if (a[i]>b[j]) g[i][j]=-200;
31: else
32: if (a[i]<b[j]) g[i][j]=200;
33: for (int i=1;i<=n;++i)
34: {
35: er^=1;
36: for (int j=0;j<=i;++j)
37: {
38: f[er][j]=f[er^1][j]+g[i][n-i+j+1];
39: if (j)
40: if (f[er^1][j-1]+g[i][j]>f[er][j])
41: f[er][j]=f[er^1][j-1]+g[i][j];
42: }
43: }
44: for (int i=0;i<=n;++i)
45: if (f[er][i]>ans)
46: ans=f[er][i];
47: printf("%d\n",ans);
48: return 0;
49: }
50: