資訊專欄INFORMATION COLUMN
摘要：動態規劃練習題匯總題目描述傳說中的九頭龍是一種特別貪吃的動物。如上圖中的輸出輸出一個整數，表示在滿足大頭的要求的前提下，九頭龍的難受值的最小值。
動態規劃練習題匯總
題目描述
傳說中的九頭龍是一種特別貪吃的動物。雖然名字叫“九頭龍”，但這只是說它出生的時候有九個頭，而在成長的過程中，它有時會長出很多的新頭，頭的總數會遠大于九，當然也會有舊頭因衰老而自己脫落。
有一天，有M個腦袋的九頭龍看到一棵長有N個果子的果樹，喜出望外，恨不得一口把它全部吃掉。可是必須照顧到每個頭，因此它需要把N個果子分成M組，每組至少有一個果子，讓每個頭吃一組。
這M個腦袋中有一個最大，稱為“大頭”，是眾頭之首，它要吃掉恰好K個果子，而且K個果子中理所當然地應該包括唯一的一個最大的果子。果子由N-1根樹枝連接起來，由于果樹是一個整體，因此可以從任意一個果子出發沿著樹枝“走到”任何一個其他的果子。
對于每段樹枝，如果它所連接的兩個果子需要由不同的頭來吃掉，那么兩個頭會共同把樹枝弄斷而把果子分開；如果這兩個果子是由同一個頭來吃掉，那么這個頭會懶得把它弄斷而直接把果子連同樹枝一起吃掉。當然，吃樹枝并不是很舒服的，因此每段樹枝都有一個吃下去的“難受值”，而九頭龍的難受值就是所有頭吃掉的樹枝的“難受值”之和。
九頭龍希望它的“難受值”盡量小，你能幫它算算嗎？
例如圖1所示的例子中，果樹包含8個果子，7段樹枝，各段樹枝的“難受值”標記在了樹枝的旁邊。九頭龍有兩個腦袋，大頭需要吃掉4個果子，其中必須包含最大的果子。即N=8，M=2，K=4：
輸入
N個果子依次編號1,2,...,N，且最大的果子的編號總是1。
果樹的形態，每行包含三個整數a (1<=a<=N)，b (1<=b<=N)，c (0<=c<=105)，表示存在一段難受值為c的樹枝連接果子a和果子b。如上圖中的 1,2,20; 1,3,4; 1,4,13; 2,5,10; 2,6,12; 3,7,15; 3,8,5
輸出
輸出一個整數，表示在滿足“大頭”的要求的前提下，九頭龍的難受值的最小值。如果無法滿足要求，輸出-1。如上圖中的難受值為4
1 思路
2 拆分子問題
3 計算
4 代碼
5 時間復雜度
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/106957.html
摘要：動態規劃練習題匯總描述有堆石子排成一排，每堆石子有一定的數量。現要將堆石子并成為一堆。合并的過程只能每次將相鄰的兩堆石子堆成一堆，每次合并花費的代價為這兩堆石子的和，經過次合并后成為一堆。 動態規劃練習題匯總 描述 有N堆石子排成一排，每堆石子有一定的數量。現要將N堆石子并成為一堆。合并的過程只能每次將相鄰的兩堆石子堆成一堆，每次合并花費的代價為這兩堆石子的和，經過N-1次合并后成為一...
摘要：動態規劃練習題總題目描述設一個個節點的二叉樹的中序遍歷為，其中數字為節點編號。若某個子樹為空，規定其加分為，葉子的加分就是葉節點本身的分數。試求一棵符合中序遍歷為且加分最高的二叉樹。 動態規劃練習題-總 題目描述設一個n個節點的二叉樹tree的中序遍歷為（1,2,3,…,n），其中數字1,2,3,…,n為節點編號。每個節點都有一個分數（均為正整數），記第i個節點的分數為di，tree及...
摘要：談到德勤與亞馬遜達成戰略合作之后的進展情況，德勤中國云服務主管合伙人劉俊龍向趣味科技透露，截至目前為止，德勤已經攜手，共同為二三十家大型企業提供了各種各樣的數字化轉型和云服務的落地，并且已經初見成效。蜀道之難，難于上青天！唐代大詩人李白這句膾炙人口的詩詞，相信也是不少傳統企業上云時的心情寫照。不過在德勤與亞馬遜AWS的攜手合作之下，傳統企業在上云與數字化轉型時遭遇的諸多痛點，正在被逐一解決。...
閱讀 5075·2021-09-07 09:58
閱讀 799·2019-08-30 15:55
閱讀 2936·2019-08-30 15:55
閱讀 928·2019-08-30 15:53
閱讀 1563·2019-08-29 12:57
閱讀 1831·2019-08-26 13:46
閱讀 574·2019-08-26 11:00
閱讀 3672·2019-08-23 15:42
