哈嘍各位親愛的讀者朋友們大家早上中午晚上好！又到了我的更新時間~今天的題目稍微有億點點難~也請感興趣的同學(xué)認(rèn)真思考一下下。今天的音樂會稍微舒緩一點，方便大家思考。讓我們點開下面的音樂，開啟今天的內(nèi)容吧！

今天，我們來對付??！木！棍！

喬治有一些同樣長的小木棍，他把這些木棍隨意砍成幾段，直到每段的長都不超過50?，F(xiàn)在，他想把小木棍拼接成原來的樣子，但是卻忘記了自己開始時有多少根木棍和它們的長度。

給出每段小木棍的長度，編程幫他找出原始木棍的最小可能長度。

輸入兩行，第一行是木棍的個數(shù)，第二行是每個木棍的長度

輸出一個數(shù)，即最小的木棍可能長度（徹底忽略50+的木棍）

example stick.in:

9

5 2 1 5 2 1 5 2 1

example stick.out

6

如果有興趣的話，請先進行一些思考，然后再往下翻看題解。

這種題的解決方案一般是DFS。但是如果你只進行單純的DFS的話，那最壞的情況下計算量就會是一個相當(dāng)恐怖的數(shù)字，超時也就是必然的了。所以，我們需要進行剪枝。

對于這道題而言，如果你將木棍從大到小進行排列復(fù)原小木棍，你就能保證同一根大木棍被小木棍拼成的時候拼的具體方案是唯一的。如果平均一根大木棍有4個小木棍組成的話，我們的計算量就能減少大約96%。（原來4個木棍有24種排列法）并且單根大木棍越長，減少的計算量越多。

要想實現(xiàn)這種效果，首先我們需要對我們收集的木棍進行排序整理。這里使用sort函數(shù)就很好。

這就夠了嗎？當(dāng)然不是！

核心的部分還在DFS里。整體而言，我的搜索工作的關(guān)鍵詞是“單調(diào)”——最開始的最大的小木棍長度必須是遞減的，在單個大木棍里拼小木棍的時候還是從大到小遞減。為了減小我們DFS的工作量，我們可以初步進行可能的長度的篩選。剛才在進行的輸入中，我已經(jīng)統(tǒng)計了木棍的總長度和最大小木棍的長度。由此我們就可以以小木棍的總長為上限，最大小木棍長為下限，將在其中間的，總長的因數(shù)（包括總長本身）作為可能的大木棍長度試圖進行木棍的復(fù)原，并且從小往大搜索，一旦搜索到可行的木棍長度即可進行輸出，結(jié)束程序。

DFS模塊里我需要4個參數(shù)跟著我走：已經(jīng)復(fù)原的木棍數(shù)量、現(xiàn)在的木棍拼出了多少、假設(shè)大木棍的長度和單調(diào)向下搜索的起點位置。結(jié)束搜索的狀態(tài)有兩種判定方式：一種是所有的木棍都已經(jīng)用完，第二種是拼上的木棍總長度等于輸入時統(tǒng)計的總長度。相比之下，我認(rèn)為第二種明顯方便不少。

在DFS過程中，我們應(yīng)該想到幾種過程中的情況：一種是拼上的木棍只剩下一點點，并且已經(jīng)沒有小木棍可以滿足它的需求了。這個時候我們就應(yīng)該結(jié)束這輪搜索——這樣拼肯定是錯的。還有一種是一根大木棍已經(jīng)拼完，這時候我們就需要及時的將木棍清空，再進行下一輪的搜索。其中拼完的大木棍計入數(shù)據(jù)，跟著變量來到下一輪DFS函數(shù)里。

當(dāng)然，更多時候我們還是需要用可能的木棍一個一個的試驗。這里寫一個for循環(huán)就行，但是UP還是會提醒一下一個非常重要的剪枝技巧——第一個木棍記得千萬不要換，就用當(dāng)前能用的最大的木棍。最后一個木棍如果能完美填滿這個大木棍的話也不要再動了——畢竟對于這個題來說，也許用更短的木棍也能達到和上面同樣的效果，但是更短的木棍憑借著他的靈活性，會有更多的用處，不是嗎？（雖然這種設(shè)定并不會節(jié)約很多時間）

具體的代碼如下（考慮到B站的代碼塊還是很不成熟，我在此先放上一個我寫的CSDN題解的備用鏈接：https://blog.csdn.net/weixin_45523749/article/details/112119255）

總體而言，這道題中可以減少計算量的地方有很多。而其中最重要的一點就是：從大到小，排好序列有序搜索。這樣就可以真正意義上做到搜索不重復(fù)了。

好啦，今天UP的文章就到這里啦！喜歡和話記得，一 ? 鍵? 三? 連? 哦！各位拜拜~~~