国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

動態(tài)規(guī)劃練習(xí)題-貪吃的九頭龍

MockingBird / 558人閱讀

摘要：動態(tài)規(guī)劃練習(xí)題匯總題目描述傳說中的九頭龍是一種特別貪吃的動物。如上圖中的輸出輸出一個整數(shù)，表示在滿足大頭的要求的前提下，九頭龍的難受值的最小值。

動態(tài)規(guī)劃練習(xí)題匯總

題目描述
傳說中的九頭龍是一種特別貪吃的動物。雖然名字叫“九頭龍”，但這只是說它出生的時候有九個頭，而在成長的過程中，它有時會長出很多的新頭，頭的總數(shù)會遠大于九，當(dāng)然也會有舊頭因衰老而自己脫落。
有一天，有M個腦袋的九頭龍看到一棵長有N個果子的果樹，喜出望外，恨不得一口把它全部吃掉。可是必須照顧到每個頭，因此它需要把N個果子分成M組，每組至少有一個果子，讓每個頭吃一組。
這M個腦袋中有一個最大，稱為“大頭”，是眾頭之首，它要吃掉恰好K個果子，而且K個果子中理所當(dāng)然地應(yīng)該包括唯一的一個最大的果子。果子由N-1根樹枝連接起來，由于果樹是一個整體，因此可以從任意一個果子出發(fā)沿著樹枝“走到”任何一個其他的果子。
對于每段樹枝，如果它所連接的兩個果子需要由不同的頭來吃掉，那么兩個頭會共同把樹枝弄斷而把果子分開；如果這兩個果子是由同一個頭來吃掉，那么這個頭會懶得把它弄斷而直接把果子連同樹枝一起吃掉。當(dāng)然，吃樹枝并不是很舒服的，因此每段樹枝都有一個吃下去的“難受值”，而九頭龍的難受值就是所有頭吃掉的樹枝的“難受值”之和。
九頭龍希望它的“難受值”盡量小，你能幫它算算嗎？
例如圖1所示的例子中，果樹包含8個果子，7段樹枝，各段樹枝的“難受值”標記在了樹枝的旁邊。九頭龍有兩個腦袋，大頭需要吃掉4個果子，其中必須包含最大的果子。即N=8，M=2，K=4：

輸入
N個果子依次編號1,2,...,N，且最大的果子的編號總是1。
果樹的形態(tài)，每行包含三個整數(shù)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

輸出
輸出一個整數(shù)，表示在滿足“大頭”的要求的前提下，九頭龍的難受值的最小值。如果無法滿足要求，輸出-1。如上圖中的難受值為4

1 思路

2 拆分子問題

3 計算

4 代碼

5 時間復(fù)雜度

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/106957.html

相關(guān)文章

  • 動態(tài)規(guī)劃練習(xí)題-總

    摘要：最近學(xué)習(xí)了動態(tài)規(guī)劃的四節(jié)網(wǎng)課，想上手練習(xí)，故寫文章留作紀念，文章的主要內(nèi)容是解題思路，代碼用寫練習(xí)題分為四種，線性動規(guī)攔截導(dǎo)彈，合唱隊形，挖地雷，建學(xué)校，劍客決斗等，區(qū)域動規(guī)石子合并，加分二叉樹，統(tǒng)計單詞個數(shù)，炮兵布陣等，樹形動規(guī)貪吃的九頭 最近學(xué)習(xí)了動態(tài)規(guī)劃的四節(jié)網(wǎng)課，想上手練習(xí)，故寫文章留作紀念，文章的主要內(nèi)容是解題思路，代碼用JS寫 練習(xí)題分為四種：1，線性動規(guī)：攔截導(dǎo)彈，合唱隊...

    yacheng 評論0 收藏0

  • 動態(tài)規(guī)劃練習(xí)題-石子合并

    摘要：動態(tài)規(guī)劃練習(xí)題匯總描述有堆石子排成一排，每堆石子有一定的數(shù)量。現(xiàn)要將堆石子并成為一堆。合并的過程只能每次將相鄰的兩堆石子堆成一堆，每次合并花費的代價為這兩堆石子的和，經(jīng)過次合并后成為一堆。 動態(tài)規(guī)劃練習(xí)題匯總 描述 有N堆石子排成一排，每堆石子有一定的數(shù)量。現(xiàn)要將N堆石子并成為一堆。合并的過程只能每次將相鄰的兩堆石子堆成一堆，每次合并花費的代價為這兩堆石子的和，經(jīng)過N-1次合并后成為一...

    ziwenxie 評論0 收藏0

  • 動態(tài)規(guī)劃練習(xí)題-加分二叉樹

    摘要：動態(tài)規(guī)劃練習(xí)題總題目描述設(shè)一個個節(jié)點的二叉樹的中序遍歷為，其中數(shù)字為節(jié)點編號。若某個子樹為空，規(guī)定其加分為，葉子的加分就是葉節(jié)點本身的分數(shù)。試求一棵符合中序遍歷為且加分最高的二叉樹。 動態(tài)規(guī)劃練習(xí)題-總 題目描述設(shè)一個n個節(jié)點的二叉樹tree的中序遍歷為（1,2,3,…,n），其中數(shù)字1,2,3,…,n為節(jié)點編號。每個節(jié)點都有一個分數(shù)（均為正整數(shù)），記第i個節(jié)點的分數(shù)為di，tree及...

    Miracle 評論0 收藏0

  • 當(dāng)企業(yè)咨詢遇上云服務(wù)：傳統(tǒng)企業(yè)的上云之道

    摘要：談到德勤與亞馬遜達成戰(zhàn)略合作之后的進展情況，德勤中國云服務(wù)主管合伙人劉俊龍向趣味科技透露，截至目前為止，德勤已經(jīng)攜手，共同為二三十家大型企業(yè)提供了各種各樣的數(shù)字化轉(zhuǎn)型和云服務(wù)的落地，并且已經(jīng)初見成效。蜀道之難，難于上青天！唐代大詩人李白這句膾炙人口的詩詞，相信也是不少傳統(tǒng)企業(yè)上云時的心情寫照。不過在德勤與亞馬遜AWS的攜手合作之下，傳統(tǒng)企業(yè)在上云與數(shù)字化轉(zhuǎn)型時遭遇的諸多痛點，正在被逐一解決。...

    figofuture 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<