题解 P2587 【[ZJOI2008]泡泡堂】
注意，楼下部分题解虽然程序对了，但是思路并不对。 部分题解写田忌赛马是错的，因为在求解己方最大值时，使用己方最弱换掉对方最强可能会浪费己方最弱的“战斗力”（指的是战胜对方最弱的可能）。 但是注意，一旦对方最弱比己方最弱更弱，那么就意味着，己方最弱的价值（两分）一定会转移到己方其他人身上（由其他人干掉对方最弱），所以己方最弱是否去打对方最强这个抉择，与己方最弱是否比对方最弱更强无关。 那么田忌赛马的贪心为什么是错的呢？ 我们试着写一下程序可以发现：田忌赛马的思路是当己方最强比不过对方最强时，用自己最弱做替补。 但是这里并没有对如果两方最强实力相等做说明（重点）。 如果我们设置田忌赛马的思路是己方最强大于等于对方最强时用己方最强换掉对方最强。那么下面的数据会出错 2 1 3 2 3 己方会选择（3->3）(1->2),而最大值是(3->2)(1->3) 如果我们设置田忌赛马的思路是己方最强大于对方最强时用己方最强换掉对方最强。小于等于时用己方最弱换掉对方最强。 2 2 3 1 3 己方会选择 (3->1)(2->3),而最大值是(3->3)(2->1)
那么就意味着如果两个最大值相等，这时候用最弱来替换不一定是最优决策，因此我们才要看最弱的情况，才有了后面的判断。 代码下面都是对的，不过有些思路有问题，特此指出。