首页 > 代码库 > 田忌赛马
田忌赛马
题目描述:
中国古代的历史故事“田忌赛马”是为大家所熟知的。话说齐王和田忌又要赛马了,他们各派出N匹马,每场比赛,输的一方将要给赢的一方200两黄金,如果是平局的话,双方都不必拿出钱。现在每匹马的速度值是固定而且已知的,而齐王出马也不管田忌的出马顺序。请问田忌该如何安排自己的马去对抗齐王的马,才能赢取最多的钱? N<=1000
解题过程:
1.首先直觉是贪心,想到3个贪心策略:
策略A:
田忌每次用最烂的马去和齐王最屌的马pk。(尽可能消耗齐王的强马)
反例是显然的,比如
田忌:1 2 3 4 4 5
齐王:3 4 4 4 6 7
按照此策略 出场顺序是 (1,7)(2,6)(3,4)(4,4)(4,4)(5,3)3败2平1胜;
而如果(1,7)(2,6)(3,4)(4,4)(4,3)(5,4)可以做到 3败1平2胜:
策略B:
田忌赛马
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。