Tian Ji -- The Horse Racing HDU

（有平局的田忌赛马，田忌赢一次得200块，输一次输掉200块，平局不得钱不输钱，要使得田忌得到最多（如果只能输就输的最少））

首先，实际是要求两人马的配对关系。那么不妨设齐王是按从快到慢的顺序出马的。因此先将齐王的马排序。

关键在于田忌最慢的马，能先赢就先赢，不能赢就去消耗齐王最快的马,
然后再来考虑最快的马，能先赢就先赢，不能赢说明现在田忌和齐王最快的
马和最慢的马都相等，再来考虑把田忌最慢的马和齐王最快的马比较。

可以发现，如果把过程当做田忌每次根据齐王出的马出一匹自己的马，那么他的的最佳策略一定是要么出剩下最快的马，要么出最慢的。（要么赢，要么消耗）

因此，把田忌的马也排一下序。之后定义ans[i][j]为齐王出i匹较强的，田忌出j匹较强的，i-j匹较弱的时能得到的最大收益。定义get(i,j)表示田忌的第i弱的马与齐王第j弱的马比，田忌得到的收益。那么ans[i][j]=max(ans[i-1][j]+get(i-j,n-i+1),ans[i-1][j-1]+get(n-j+1,n-i+1))。

小细节：

齐王出第i强的（第n-i+1弱的）时：
如果田忌出弱的，那么田忌已经出了j匹较强的，这一次出的是第i-j匹弱的
如果田忌出强的，那么这一次出的是第j强的（第n-j+1弱的）

对于ans[i][0]和ans[i][i]要特判，不然会越界访问。

这题有$O(nlogn)$（除去排序就是$O(n)$）的完全贪心做法。（仅做记录）

曾经错误：

1.把get里面的t1和t2打成全是t1。
2.进行动态规划的循环中前后两行特判写错，写成
ans[i][0]=ans[i-1][0]+get(i-j,n-i+1)
ans[i][i]=ans[i-1][i-1]+get(n-j+1,n-i+1)

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 int ans[1010][1010];
 6 int t1[1010],t2[1010];
 7 int n,anss;
 8 int get(int a,int b)
 9 {
10     if(t1[a]>t2[b])    return 200;
11     if(t1[a]==t2[b])    return 0;
12     return -200;
13 }
14 int main()
15 {
16     int i,j;
17     scanf("%d",&n);
18     while(n!=0)
19     {
20         anss=-0x3f3f3f3f;
21         memset(ans,0,sizeof(ans));
22         for(i=1;i<=n;i++)
23             scanf("%d",&t1[i]);
24         for(i=1;i<=n;i++)
25             scanf("%d",&t2[i]);
26         sort(t1+1,t1+n+1);
27         sort(t2+1,t2+n+1);
28         for(i=1;i<=n;i++)
29         {
30             ans[i][0]=ans[i-1][0]+get(i,n-i+1);
31             for(j=1;j<i;j++)
32                 ans[i][j]=max(ans[i-1][j]+get(i-j,n-i+1),ans[i-1][j-1]+get(n-j+1,n-i+1));
33             ans[i][i]=ans[i-1][i-1]+get(n-i+1,n-i+1);
34         }
35         for(i=0;i<=n;i++)
36             anss=max(anss,ans[n][i]);
37         printf("%d
",anss);
38         scanf("%d",&n);
39     }
40     return 0;
41 }