資訊專欄INFORMATION COLUMN
摘要：動(dòng)態(tài)規(guī)劃練習(xí)題匯總題目描述傳說中的九頭龍是一種特別貪吃的動(dòng)物。如上圖中的輸出輸出一個(gè)整數(shù)，表示在滿足大頭的要求的前提下，九頭龍的難受值的最小值。
動(dòng)態(tài)規(guī)劃練習(xí)題匯總
題目描述
傳說中的九頭龍是一種特別貪吃的動(dòng)物。雖然名字叫“九頭龍”，但這只是說它出生的時(shí)候有九個(gè)頭，而在成長的過程中，它有時(shí)會(huì)長出很多的新頭，頭的總數(shù)會(huì)遠(yuǎn)大于九，當(dāng)然也會(huì)有舊頭因衰老而自己脫落。
有一天，有M個(gè)腦袋的九頭龍看到一棵長有N個(gè)果子的果樹，喜出望外，恨不得一口把它全部吃掉?？墒潜仨氄疹櫟矫總€(gè)頭，因此它需要把N個(gè)果子分成M組，每組至少有一個(gè)果子，讓每個(gè)頭吃一組。
這M個(gè)腦袋中有一個(gè)最大，稱為“大頭”，是眾頭之首，它要吃掉恰好K個(gè)果子，而且K個(gè)果子中理所當(dāng)然地應(yīng)該包括唯一的一個(gè)最大的果子。果子由N-1根樹枝連接起來，由于果樹是一個(gè)整體，因此可以從任意一個(gè)果子出發(fā)沿著樹枝“走到”任何一個(gè)其他的果子。
對于每段樹枝，如果它所連接的兩個(gè)果子需要由不同的頭來吃掉，那么兩個(gè)頭會(huì)共同把樹枝弄斷而把果子分開；如果這兩個(gè)果子是由同一個(gè)頭來吃掉，那么這個(gè)頭會(huì)懶得把它弄斷而直接把果子連同樹枝一起吃掉。當(dāng)然，吃樹枝并不是很舒服的，因此每段樹枝都有一個(gè)吃下去的“難受值”，而九頭龍的難受值就是所有頭吃掉的樹枝的“難受值”之和。
九頭龍希望它的“難受值”盡量小，你能幫它算算嗎？
例如圖1所示的例子中，果樹包含8個(gè)果子，7段樹枝，各段樹枝的“難受值”標(biāo)記在了樹枝的旁邊。九頭龍有兩個(gè)腦袋，大頭需要吃掉4個(gè)果子，其中必須包含最大的果子。即N=8，M=2，K=4：
輸入
N個(gè)果子依次編號1,2,...,N，且最大的果子的編號總是1。
果樹的形態(tài)，每行包含三個(gè)整數(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
輸出
輸出一個(gè)整數(shù)，表示在滿足“大頭”的要求的前提下，九頭龍的難受值的最小值。如果無法滿足要求，輸出-1。如上圖中的難受值為4
1 思路
2 拆分子問題
3 計(jì)算
4 代碼
5 時(shí)間復(fù)雜度
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/106957.html
摘要：最近學(xué)習(xí)了動(dòng)態(tài)規(guī)劃的四節(jié)網(wǎng)課，想上手練習(xí)，故寫文章留作紀(jì)念，文章的主要內(nèi)容是解題思路，代碼用寫練習(xí)題分為四種，線性動(dòng)規(guī)攔截導(dǎo)彈，合唱隊(duì)形，挖地雷，建學(xué)校，劍客決斗等，區(qū)域動(dòng)規(guī)石子合并，加分二叉樹，統(tǒng)計(jì)單詞個(gè)數(shù)，炮兵布陣等，樹形動(dòng)規(guī)貪吃的九頭 最近學(xué)習(xí)了動(dòng)態(tài)規(guī)劃的四節(jié)網(wǎng)課，想上手練習(xí)，故寫文章留作紀(jì)念，文章的主要內(nèi)容是解題思路，代碼用JS寫 練習(xí)題分為四種：1，線性動(dòng)規(guī)：攔截導(dǎo)彈，合唱隊(duì)...
摘要：動(dòng)態(tài)規(guī)劃練習(xí)題匯總描述有堆石子排成一排，每堆石子有一定的數(shù)量?，F(xiàn)要將堆石子并成為一堆。合并的過程只能每次將相鄰的兩堆石子堆成一堆，每次合并花費(fèi)的代價(jià)為這兩堆石子的和，經(jīng)過次合并后成為一堆。 動(dòng)態(tài)規(guī)劃練習(xí)題匯總 描述 有N堆石子排成一排，每堆石子有一定的數(shù)量。現(xiàn)要將N堆石子并成為一堆。合并的過程只能每次將相鄰的兩堆石子堆成一堆，每次合并花費(fèi)的代價(jià)為這兩堆石子的和，經(jīng)過N-1次合并后成為一...
摘要：動(dòng)態(tài)規(guī)劃練習(xí)題總題目描述設(shè)一個(gè)個(gè)節(jié)點(diǎn)的二叉樹的中序遍歷為，其中數(shù)字為節(jié)點(diǎn)編號。若某個(gè)子樹為空，規(guī)定其加分為，葉子的加分就是葉節(jié)點(diǎn)本身的分?jǐn)?shù)。試求一棵符合中序遍歷為且加分最高的二叉樹。 動(dòng)態(tài)規(guī)劃練習(xí)題-總 題目描述設(shè)一個(gè)n個(gè)節(jié)點(diǎn)的二叉樹tree的中序遍歷為（1,2,3,…,n），其中數(shù)字1,2,3,…,n為節(jié)點(diǎn)編號。每個(gè)節(jié)點(diǎn)都有一個(gè)分?jǐn)?shù)（均為正整數(shù)），記第i個(gè)節(jié)點(diǎn)的分?jǐn)?shù)為di，tree及...
摘要：談到德勤與亞馬遜達(dá)成戰(zhàn)略合作之后的進(jìn)展情況，德勤中國云服務(wù)主管合伙人劉俊龍向趣味科技透露，截至目前為止，德勤已經(jīng)攜手，共同為二三十家大型企業(yè)提供了各種各樣的數(shù)字化轉(zhuǎn)型和云服務(wù)的落地，并且已經(jīng)初見成效。蜀道之難，難于上青天！唐代大詩人李白這句膾炙人口的詩詞，相信也是不少傳統(tǒng)企業(yè)上云時(shí)的心情寫照。不過在德勤與亞馬遜AWS的攜手合作之下，傳統(tǒng)企業(yè)在上云與數(shù)字化轉(zhuǎn)型時(shí)遭遇的諸多痛點(diǎn)，正在被逐一解決。...
閱讀 5472·2021-09-07 09:58
閱讀 870·2019-08-30 15:55
閱讀 3164·2019-08-30 15:55
閱讀 1051·2019-08-30 15:53
閱讀 1648·2019-08-29 12:57
閱讀 2002·2019-08-26 13:46
閱讀 648·2019-08-26 11:00
閱讀 3748·2019-08-23 15:42
