【描述】
中國古代的歷史故事“田忌賽馬”是為大家所熟知的。話說齊王和田忌又要賽馬了，他們各派出N匹馬，每場比賽，輸?shù)囊环綄⒁o贏的一方200兩黃金，如果是平局的話，雙方都不必拿出錢。現(xiàn)在每匹馬的速度值是固定而且已知的，而齊王出馬也不管田忌的出馬順序。請問田忌該如何安排自己的馬去對抗齊王的馬，才能贏取最多的錢？
【輸入】
第一行為一個正整數(shù)n (n <= 2000) ，表示雙方馬的數(shù)量。
第二行有N個整數(shù)表示田忌的馬的速度。
第三行的N個整數(shù)為齊王的馬的速度。
【輸出】
僅有一行，為田忌賽馬可能贏得的最多的錢，結(jié)果有可能為負(fù)。
【樣例輸入】
3
92 83 71
95 87 74
【樣例輸出】
200
【分析】
如果齊王的馬是按速度排序之后，從高到低被派出的話，田忌一定是將他馬按速度排序之后，從兩頭取馬去和齊王的馬比賽。
n設(shè)f[i,j]表示齊王按從強到弱的順序出馬和田忌進行了i場比賽之后，從“頭”取了j匹較強的馬，從“尾”取了i-j匹較弱的馬，所能夠得到的最大盈利。
n狀態(tài)轉(zhuǎ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: