对Iarsr题解的个人理解
查看原帖
对Iarsr题解的个人理解
245712
fdc99楼主2024/11/25 17:51

(Iarsr) Happy Card 题解

首先 4 张牌出可以算成 三带一 ,这样我们就可以重新定义一下三带一操作,即三张牌带任意一张牌(可以是与这三张牌同号的)

问题就变成了三带一,出2张,出1张,如何做可以把牌出完并且次数尽可能小,我们把牌分一下类可以更好的考虑问题

1张牌放在一起,2张牌放在一起,3张牌放在一起,对于大于三张牌的我们可以把他拆成若干个3张牌和1张牌(或两张牌)

考虑3张牌的牌堆,三带一操作可以让我们减少操作次数,先匹配三带一

  1. 3张牌匹配1张牌,可以让原本3次操作(只考虑3张和1张,要出1次2张和2次1张)变成一次操作
  2. 3张牌匹配2张牌,可以理解为3张牌抽走2张牌的一张,虽然无论抽走还是不抽,2张牌都只用抽一次,但是抽走之后3张牌出牌可以用三带一减少次数
  3. 只有3张牌,这时我们有两种选择,可以直接出或者互相匹配,我们可以推一下哪种情况更优

假设有两堆是3张牌,直接出的次数是 1 + 1 + 1 + 1 (先出2张再出1张),如果是互相匹配则是 1 + 1 , (把其中一堆拆成 1 + 2,把1给3张牌出三带一,剩下的1张直接出),显然后者更优更优

PS: 原题解这里直接说达到答案下界我也不知道啥意思,只能列个式子说明确实互相匹配更优,如果有dalao可以来解答一下(

接着如果还剩下2张或1张的牌直接出就是最优

2024/11/25 17:51
加载中...