在5月20日這一天,狼人想向小紅帽表白,於是打算用無限流疊5201314層狂怒上限。
狼人的思路:起手分岔路口最左,用偏執-分岔路口刷特效藥得到足夠的行動力,然後就可以印潛伏和獨行刷狂怒上限了。
從而構築卡組:分岔路口×2,偏執,獨行(+1狂怒上限),潛伏(×2狂怒上限),
考慮一共5卡,所以攜帶祝福:特效藥,鹿之輕盈or沉重寶箱
但是狼人突然意識到一個問題,分岔路口印卡只能按手卡順序從右往左印,而且在印下一張卡後必須先用掉之前印的卡,這樣就只能先印很多潛伏,用完潛伏再用獨行。於是狼人算了算最近的2的次方數:4194304=2^22,與目標值相差1007010——這意味著先印21張潛伏,用完後再印1007010張獨行(就算用月之輪迴也要50w+卡)。可行、但沒必要——狼人如此想到。那麼能不能印完潛伏就印獨行,把所有卡留在最後用呢?
翻翻圖鑑,是記憶破碎!它可以把一張卡移除,獲得兩張臨時的卡,而新卡會出現在手牌最右端,只要印完潛伏,對獨行使用記憶破碎,就可以印獨行了。於是狼人往卡組裡加入了一張記憶破碎,相應的祝福改為:特效藥,鹿之輕盈and沉重寶箱。
狼人自我感覺很滿意,決定雲一下流程。
倒推法:對目標值做如下處理,若為偶數則除以2,若為奇數則減去1。得到下表
其中A表示潛伏,B表示獨行,反過來寫就得到了操作序列:
AABABABABAABAABABABAABABAABAAAABA.
流程也雲好了,那麼...有沒有更簡單的操作序列呢?狼人不禁這麼想到。
如果按這個流程,相當於對2先乘2次2再加1,對所得結果乘2再加1...
用算式表示就是:
於是抽象出一般的問題:
對初始值x進行有限次運算A和B,其中A表示乘2,B表示+1。
那麼得到目標值z的最簡步驟是什麼?
問題的實質是:對z做如下分解
取初始值x=2(對應初始狂怒上限為2)
其中ABCDE...代表運算乘2的次數,而abcde...代表運算+1的次數,自然都是非負整數。
然後求操作次數w=A+B+C...+a+b+c..的最小值。
首先是問題的有解性:
任何一個數都可以通過有限次B運算得到,此時A=B=C=...=0,z=2+a+b+c...=x+w即w=z-2
然後考慮abcde...的取值,猜想:在最優的情況下只能取0或者1(即倒推法為最優解)
先證明對a的時候猜想成立,設a≥2,
首先,設
對2進行A次乘2操作,a次+1操作後得到z1,步數
然後考慮採用倒推法對z1進行處理所得的步數
情況1:設,則
,步數
註:這裡實際上只對z1進行了一次逆推處理,並未對所得結果進一步處理。
而
這說明了a取偶數時,採用倒推法確實會讓步數不增。
情況2:a為奇數時,同理可得。
用歸納法易得各個小寫字母abcde...在最優時只能取0或1。
進一步考慮ABCDE...的取值,易得:最優情況下ABCDE...之和m滿足
即A運算的次數總和為定值。
回歸原問題,目標值z取5201314,倒推法所得操作序列為
AABABABABAABAABABABAABABAABAAAABA.
其中有21個A,12個B,如果要優化,那麼勢必要刪除後位的B,同時把在被刪除的B之前的某個A與它前面的某個B換位置,才能達到值先減後增的效果——才可能達到目標值。
一方面所得新序列必須有連續的B操作(否則根據倒推法的唯一性這樣的序列是不存在的),另一方面此時必然存在某個小寫字母i≥2,這與最優情況下abcde...的取值只能為0或1矛盾,從而得到了新序列不存在的結論。
綜上所述,倒推法確實是初始值x=2的情況下最優解。
想到這裡,狼人不禁舒了一口氣,一想到自己將用最簡潔的方法、最少的步驟得到5201314層狂怒便滿心歡喜。
小紅帽一定會喜歡這份禮物吧!