動態(tài)規(guī)劃及其應(yīng)用-在線瀏覽
2024-09-15 03:45本頁面
【正文】 的合并步驟： 第一次合并 3 4 6 5 4 2 2,3合并得分是５ 第二次合并 5 4 6 5 4 5,4合并得分是 9 第三次合并 9 6 5 4 5,4合并得分是 9 第四次合并 9 6 9 9,6合并得分是 15 第五次合并 15 9 15,9合并得分是 24 總得分＝ 5＋ 9＋ 9＋ 15＋ 24＝ 62 但是如果采用如下合并方法，卻可以得到比上面得分更少的方法： 第一次合并 3 4 6 5 4 2 3,4合并得分是 7 第二次合并 7 6 5 4 2 7,6合并得分是 13 第三次合并 13 5 4 2 4,2合并得分是 6 第四次合并 13 5 6 5,6合并得分是 11 第五次合并 13 11 13,11合并得分是 24 總得分＝ 7＋ 13＋ 6＋ 11＋ 24＝ 61 ? 顯然，貪心法是錯誤的。 ? 具體來說我們應(yīng)該定義一個數(shù)組 s[i,j]用來表示合并方法， i表示從編號為第 i堆的石頭開始合并，j表示從 i開始數(shù) j堆進(jìn)行合并， s[i,j]為合并的最優(yōu)得分。 ? 由此得到算法框架如下： For j←2 to n do {枚舉階段，從兩兩合并開始計算 } For i←1 to n do {計算當(dāng)前階段的 n種不同狀態(tài)的值 } For k←1 to j 1 do {枚舉不同的分段方法 } begin If i+kn then t←(i+k) mod n else t←i+k { 最后一個連第一個的情況處理 } s[i,j]← 最優(yōu) {s[i,k]+s[t,jk]+sum[1,3]} {sum[i,j]表示從 i開始數(shù) j個數(shù)的和 } end。在項鏈上有 N顆能量珠。并且，對于相鄰的兩顆珠子，前一顆珠子的尾標(biāo)記一定等于后一顆珠子的頭標(biāo)記。如果前一顆能量珠的頭標(biāo)記為 m，尾標(biāo)記為 r，后一顆能量珠的頭標(biāo)記為 r，尾標(biāo)記為 n，則聚合后釋放的能量為（ Mars單位），新產(chǎn)生的珠子的頭標(biāo)記為 m，尾標(biāo)記為 n。顯然，不同的聚合順序得到的總能量是不同的，請你設(shè)計一個聚合順序，使一串項鏈釋放出的總能量最大。我們用記號 ⊕表示兩顆珠子的聚合操作， (j⊕ k)表示第 j， k兩顆珠子聚合后所釋放的能量。 這一串項鏈可以得到最優(yōu)值的一個聚合順序所釋放的總能量為 ((4⊕ 1)⊕ 2)⊕ 3） =10*2*3+10*3*5+10*5*10=710。第二行是 N個用空格隔開的正整數(shù)，所有的數(shù)均不超過 1000。第 N顆珠子的尾標(biāo)記應(yīng)該等于第 1顆珠子的頭標(biāo)記。 【 輸出文件 】 輸出文件 ，是一個正整數(shù) E（ E≤*109），為一個最優(yōu)聚合順序所釋放的總能量。//計算鏈的終點 if(j=2*n)//若在最大值范圍內(nèi) for p=k to j1 //枚舉斷開點 begin 根據(jù)方程更新 f[k,j]的值 。 end。每個節(jié)點都有一個分?jǐn)?shù)（均為正整數(shù)），記第 i個節(jié)點的分?jǐn)?shù)為 di， tree及它的每個子樹都有一個加分，任一棵子樹subtree（也包含 tree本身）的加分計算方法如下： ? subtree的左子樹的加分 subtree的右子樹的加分＋ subtree的根的分?jǐn)?shù) ? 若某個子樹為空，規(guī)定其加分為 1，葉子的加分就是葉節(jié)點本身的分?jǐn)?shù)。 ? 試求一棵符合中序遍歷為（ 1,2,3,…,n ）且加分最高的二叉樹 tree。 ? 第 2行： n個用空格隔開的整數(shù)，為每個節(jié)點的分?jǐn)?shù)（分?jǐn)?shù)＜ 100）。 ? 第 2行： n個用空格隔開的整數(shù)，為該樹的前序遍歷。如果用數(shù)組 f[i,j]表示從節(jié)點 i到節(jié)點 j所組成的二叉樹的最大加分，枚舉根節(jié)點，則動態(tài)方程可以表示如下： ? f[i,j]=max{i=t=j | d[t]+f[i,t1]*f[t+1,j]} ? 初始： f(i,i)=d[i] ? 目標(biāo)： f(1,n) ? procedure dfs(l,r:integer)。 ? s:int64。//實現(xiàn)記憶化 ? if l=r then //處理邊界 ? begin ? f[l,r]:=a[l]。 ? exit。 ? for i:=l to r do ? begin ? s:=0。s:=f[l,i1]。//處理左子樹的加分 ? if ri0 then begin dfs(i+1,r)。end。 ? if sf[l,r] then ? begin f[l,r]:=s。 end。 ? end。 ? 葉－ 根：既把根的子節(jié)點傳遞有用的信息給根，完成后根得出最優(yōu)解的過程。（樹的后序遍歷求解） Ural 1018 二叉蘋果樹 ? 【 問題描述 】 ? 有一棵蘋果樹，如果樹枝有分叉，一定是分 2叉（就是說沒有只有 1個兒子的結(jié)點）這棵樹共有 N個結(jié)點（葉子點或者樹枝分叉點），編號為 1N,樹根編號一定是 1。下面是一顆有 4個樹枝的樹 2 5 \ / 3 4 \ / 1 現(xiàn)在這顆樹枝條太多了，需要剪枝。 給定需要保留的樹枝數(shù)量，求出最多能留住多少蘋果。 N表示樹的結(jié)點數(shù)， Q表示要保留的樹枝數(shù)量。 每行 3個整數(shù)，前兩個是它連接的結(jié)點的編號。 每根樹枝上的蘋果不超過 30000個。 ? 樣例輸入 ? 5 2 1 3 1 1 4 10 2 3 20 3 5 20 ? 樣例輸出 ? 21 ? 分析： ? 因為題目一給出就是純二叉的樹結(jié)構(gòu)，如果要保留住最多蘋果數(shù)量，必然是左子樹保留盡量多，右子樹也保留盡量多，滿足最優(yōu)性原理 ,我們定義狀態(tài) ,f[i,j]表示以 i為根的子樹 (還包括 [i與 i的父親 ] 這條邊 )內(nèi) ,保存 j條邊最多可以有多少蘋果 ,顯然f[i,j]=max(f[left[i],k]+f[right[i],jk1])+apple[i,father[i]]。f[i,0]=0。虛擬了一條邊，也就相當(dāng)于多添加了一個節(jié)點 1的父親節(jié)點，這條邊為 1和它父親節(jié)點的 ? procedure tree_dp(t,k:integer)。 ? begin ? if f[t,k]0 then exit。 exit。 ? f[t,k]:=0。//左子樹 ? t
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1