【HDU 3993】田忌赛马 题解+勘误

应同学之邀帮忙发布的一篇勘误 【HDU 3993】田忌赛马 题解+勘误 题解这里就略写一下了，主要是勘误。 这道题是2011年之前的多校训练题，2020年的今天，我们一个集训队全部挂在上面了。最后在HDU看到了9年前的讨论区，才知道这题有如下问题： speed is unique 这句话是假的（不然哪里来的平局） 平局不会给钱，也就是说题目描述里说平局了给1块钱是假的 在网上搜不到这样的更正信息（除了HDU的讨论区，用vj提交的用户很难发现），所以把勘误放出来，免得大家连怎么WA的都不知道。 然后说一些提示： 数据很小，可以考虑状态压缩+记忆化搜索 直接定义二维状态有很多浪费的空间，可以考虑u 【田忌赛马】是一道源自古代中国历史的著名策略问题，被转化为计算机科学中的算法题目，出现在HDU（杭州电子科技大学在线评测系统）的3993号问题中。该题目的主要目的是通过编程来解决如何在不确定的对手策略下，通过合理安排马匹的出战顺序，使田忌在三场比赛中获得最大的收益。然而，题目本身存在一些误导性的描述，导致许多参赛者在解答时遇到困扰。 题目中提到“speed is unique”，即每匹马的速度都是唯一的，这是一个错误的信息。实际上，如果速度都是唯一的，那么比赛结果将是确定的，不存在平局的情况。因此，正确的理解应该是马的速度可能相同，导致可能出现平局的结果。需要注意的是，平局并不会带来任何收益，与题目描述中的“平局给1块钱”不符。 在解决这个问题时，由于数据规模较小，可以采用状态压缩和记忆化搜索的方法来优化算法。状态压缩是将多维状态用一维整数表示，以节省存储空间。对于这个问题，可以考虑使用位运算来实现状态压缩，每匹马的状态可以用一位来表示，0代表未出场，1代表出场且输，2代表出场且赢。这样可以有效地减少状态的数量，降低空间复杂度。 记忆化搜索则是通过动态规划来避免重复计算，提高效率。在这个问题中，我们可以定义一个状态数组dp，其中dp[i][mask]表示前i场比赛结束，田忌的马匹状态为mask时，他能获得的最大期望收益。在遍历所有可能的决策和比赛结果时，更新dp数组的值，从而得到最优解。 另外，据作者Karshilov所述，田忌的决策似乎不会影响期望值，但这需要进一步的分析验证。即使如此，为了解决问题，我们可以按照最简单的策略，每次都派出田忌最弱的马，以此来模拟对手可能的选择，最终也能得到正确的答案。但如果尝试在每个状态中枚举田忌的所有可能决策并取最优期望值，可能会导致超时错误（TLE）。 解决【HDU 3993】田忌赛马的关键在于正确理解题目的误导性描述，尤其是关于马匹速度和平局的处理，以及采用合适的数据结构（如unordered_map）和算法（状态压缩、记忆化搜索）来优化代码，以确保在有限的时间内求解出最优解。