田忌赛马

田忌赛马[1]

【问题描述】大家都知道“田忌赛马”的故事。现在，田忌再一次和齐王赛马。他们各派出 N 匹马（N≤2000）。

每场比赛，输的一方将要给赢的一方200两黄金，如果是平局的话，双方都不必拿出钱。

每匹马的速度值是固定而且已知的，而齐王出马也不管田忌的出马顺序。请问田忌该如何安排自己的马去对抗齐王的马，才能赢最多的钱？

【分析】[2]

题目本身已经告诉我们怎样用二分图最佳匹配来解决这个问题——把田忌的马放左边，把齐王的马放右边，田忌的马 A 和齐王的 B 之间，如果田忌的马胜，则连一条权为200的边；如果平局，则连一条权为0的边；如果输，则连一条权为－200的边。

但是题目告诉我们没有必要这样做，我们也无法这样做（复杂度很高，无法承受N＝2000的规模）。

我们不妨用贪心思想来分析一下问题。因为田忌掌握有比赛的“主动权”，他总是根据齐王所出的马来分配自己的马，所以这里不妨认为齐王的出马顺序是按马的速度从高到低出的。由这样的假设，我们归纳出如下贪心策略：

1.  如果田忌剩下的马中最强的马都赢不了齐王剩下的最强的马，那么应该用最差的一匹马去输给齐王最强的马。

2.  如果田忌剩下的马中最强的马可以赢齐王剩下的最强的马，那就用这匹马去赢齐王剩下的最强的马。  

3.  如果田忌剩下的马中最强的马和齐王剩下的最强的马打平，可以选择打平或者用最差的马输掉比赛。我们发现，第三个贪心策略出现了一个分支：打平或输掉。如果穷举所有的情况，算法的复杂度将比求二分图最佳匹配还要高；如果一概而论的选择让最强的马去打平比赛或者是让最差的马去输掉比赛，则存在反例。

虽然因为第三个贪心出现了分支，我们不能直接的按照这种方法来设计出一个完全贪心的方法，但是通过上述的三种贪心策略，我们可以发现，如果齐王的马是按速度排序之后，从高到低被派出的话，田忌一定是将他马按速度排序之后，从两头取马去和齐王的马比赛。有了这个信息之后，动态规划的模型也就出来了！

设 f(i,j)表示田忌从“头”取了 i 匹较强的马，从“尾”取了 j匹较弱的马进行比赛所能够得到的最大盈利，

则状态转移方程为：f(i,j)＝max{ f(i,j-1)+g[n-(j-1)], f(i-1,j)+g(i)}

其中 g(x)表示田忌的第x 匹马和齐王的第 i＋j 匹马（此时正是第 i＋j 场比赛）分别按照由强到弱的顺序排序之后，田忌所能取得的盈利，胜为200，输为－200，平为0。

---

[1] 题目来源：ACM2004上海赛区，有删改。

[2] 选自黄劲松《贪婪的动态规划》，有改动。