leet_870

README

题目链接

题解

看到这道题，我瞬间想到了以前高中参加NOIP时做过的一道题“田忌赛马”。分别告知田忌和齐王每匹马的速度，假如：

• 田忌赢一场得1分
• 输一场得 -1分
• 打平得0分

问田忌最多能得多少分

这题和田忌赛马几乎一模一样，“最大优势”其实就是田忌赛马里田忌的最大得分。只是和田忌赛马不同的是，这道题没有“打平”一说。没有“打平”，那这道题就比田忌赛马简单了很多很多。可以来分析一下：

先把A,B按从大到小的顺序进行排序，有一个很容易想到的贪心策略就是：

• 如果A当前的最大值，比B当前的最大值大，那么A就用这个最大的去对位B的最大值。为什么呢？因为A的最大值比B的最大值都大，也就是说比B所有的值都大，也就是说对位B的任意一个值都是占优势，那么肯定要尽量消耗掉B的最大值，这样剩下的赢面更大。
• 如果A中没有值能大过B的最大值，也就是说，无论A中哪个值和B的最大值对位都是输，那干脆就用最小的去消耗掉B最大的。

做个类比，想必斗地主大家都玩过，假设对方手里有一张2，你手上有一张3和一张A，这时该你出，你是出3还是出A呢？很显然你会出3，对手出2之后你的A就是大牌了。也就是说：

• 如果赢，就赢对方最大的
• 如果输，就用最小的去输给对方最大的

反正每次消耗掉它最大的。

这道题就是这么一个简单的贪心。稍微需要注意的是，B的顺序的给定的，因此我们可以先记录下B的原始顺序，然后copy一份用来进行排序和贪心，最后得到的结果是针对“B”是降序时的结果给的，你要利用原始B的顺序还原回去。

对于本题的讨论到此结束，下面是与这道题类似的“田忌赛马”

那么这道题和田忌赛马的区别在哪里呢？—— 打平

这道题的"优势"是A[i]>B[i]，相等的情况不算优势，也就是说，要么“优势”要么“非优势”，只有两种可能。 田忌赛马有三种可能，胜 平 负。在两匹马打平的情况下，到底是真的让这两匹马打平呢，还是拿最慢的马来输给齐王当前这匹马，这个需要根据剩余的马而定，比如：

• 田忌： 8 2 1
• 齐王： 8 7 1

如果田忌用8和齐王的8进行比赛，打平，剩余的场次最多得0分，总得分是0。 如果田忌用1输给齐王的8， 剩下的比赛就变成： 田忌：8 2 齐王：7 1 总得分就是-1+1+1=1，所以这种case田忌就应该拿最弱的马去输。

对于下面这个例子：

• 田忌：8 5 4
• 齐王：8 4 3

这种情况下，就应该用8和8来打平，总得分是0+1+1=2

所以你可以看到，在两匹马在打平的情况下，需要在两种case下取最优。这就比较适合记忆化搜索了。

设f(i,j,m,n)表示田忌的第i匹马到第j匹和齐王的第m到第n匹马比赛能得到的最高分。 但是仔细想一下，我们对数组进行降序排序后，齐王每次都是出第一匹马，也就是最快的那匹。假设田忌和齐王分别共有K+1匹马，当田忌第0到i-1匹最快的马已经出了，第j+1到第K匹最慢的马也出了，很容易能算出，田忌一共出了i-1-0+1 + K-(j+1)+1 = i+K-j匹马，也就是说齐王下一匹会出的马是第i+K-j+1匹马（但是数组下标从0开始，所以是B[i+K-j]）。这样你会发现，我们一开始的f(i,j,m,n)可以减掉两维，用f(i,j)就可以表示了，K是一个常数。状态转移方程也就很容易写出来了： f(i,j) =

• 1+f(i+1,j) (A[i]>B[i+K-j])
• -1+f(i,j-1) (A[i]<B[i+K-j])
• Max{0+f(i+1,j), -1+f(i,j-1)} (A[i]=B[i+K-j])