【tyvj1048】田忌赛马

2013年11月23日2,7672

题目描述

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

输入

第一行为一个正整数n  (n  < =  1000)  ,表示双方马的数量。 第二行有N个整数表示田忌的马的速度。 第三行的N个整数为齐王的马的速度。

输出

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

样例输入

3 92 83 71 95 87 74

样例输出

200
9018题库的田忌赛马,如果田忌输了,输出0,且似乎n<=3000。TYVJ随意
本题原来是用贪心的思路,用田忌速度从小到大的每一匹马去战胜或打平齐王的最强的马
像这样

是有反例的,因为看不符合历史上赛马的典故,用这种方法下等马变成和下等马赛平了,显然不妥。

但是用最弱的马故意输最强的马当然也是不可取的。

网上有种贪心做法是这样

1、开始也是先排序,可以使用sort快排;
2、然后将田忌最大的马与国王进行比较;
3、如果田忌最大的马大于国王,那么就胜场++;
4、如果田忌最大的马小于国王,那么就一定会输,所以用田忌最小的马输给国王最大的马;
5、如果田忌最大的马等于国王,那么就比较最小的马;
5。1、如果田忌最小的马大于国王,那么胜场++;
5。2、如果田忌最小的马小于国王,那么就输给国王;
5。3、如果田忌最小的马等于国王,就用田忌最小的马对国王最大的马,如果国王最大的马大,那么财产要减200;
还有动规的

1.思路
不妨用贪心思想来分析一下问题。因为田忌掌握有比赛的“主动权”,他总是根据齐王所出的马来分配自己的马,所以这里不妨认为齐王的出马顺序是按马的速度从高到低出的。由这样的假设,我们归纳出如下贪心策略:
如果田忌剩下的马中最强的马都赢不了齐王剩下的最强的马,那么应该用最差的一匹马去输给齐王最强的马。
如果田忌剩下的马中最强的马可以赢齐王剩下的最强的马,那就用这匹马去赢齐王剩下的最强的马。
如果田忌剩下的马中最强的马和齐王剩下的最强的马打平的话,可以选择打平或者用最差的马输掉比赛。
2.反例
光是打平的话,如果齐王马的速度分别是1 2 3,田忌马的速度也是1 2 3,每次选择打平的话,田忌一分钱也得不到,而如果选择先用速度为1的马输给速度为3的马的话,可以赢得200两黄金。
光是输掉的话,如果齐王马的速度分别是1 3,田忌马的速度分别是2 3,田忌一胜一负,仍然一分钱也拿不到。而如果先用速度为3的马去打平的话,可以赢得200两黄金。

3.解决方案
通过上述的三种贪心策略,我们可以发现,如果齐王的马是按速度排序之后,从高到低被派出的话,田忌一定是将他马按速度排序之后,从两头取马去和齐王的马比赛。有了这个信息之后,动态规划的模型也就出来了!

4.DP方程
设f[i,j]表示齐王按从强到弱的顺序出马和田忌进行了i场比赛之后,从“头”取了j匹较强的马,从“尾”取了i-j匹较弱的马,所能够得到的最大盈利。
状态转移方程如下:
F[I,j]=max{f[i-1,j]+c[n-(i-j)+1,i],f[i-1,j-1]+c[j,i]}
其中g[i,j]表示田忌的马和齐王的马分别按照由强到弱的顺序排序之后,田忌的第i匹马和齐王的第j匹马赛跑所能取得的盈利,胜为1,输为-1,平为0。
结果用最大的乘以200即可。

5.解释

为什么F[I,j]=max{f[i-1,j]+c[n-(i-j)+1,i],f[i-1,j-1]+c[j,i]}可以呢?

因为你无论怎么样都是从前或者从后面取马,而F[I,j]=max{f[i-1,j]+c[n-(i-j)+1,i],f[i-1,j-1]+c[j,i]}这个方程把所有可能的贪心情况都表示出来了。

 

  • oh-god李2013年11月24日 上午10:28 回复

    我了去,啥时候改版的?

    #1  
    • hzw2013年11月24日 上午11:44 回复
      admin

      上次数据丢失了就顺便换了个主题。。

      #11