leet_870

package
v0.0.0-...-9cc4e77 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: May 14, 2019 License: MIT Imports: 1 Imported by: 0

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])

Documentation

The Go Gopher

There is no documentation for this package.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL