動態(tài)規(guī)劃及其應(yīng)用(編輯修改稿)
2024-09-01 03:45 本頁面
【文章內(nèi)容簡介】 *n do //枚舉鏈的起點(diǎn) begin j=k+d1。//計算鏈的終點(diǎn) if(j=2*n)//若在最大值范圍內(nèi) for p=k to j1 //枚舉斷開點(diǎn) begin 根據(jù)方程更新 f[k,j]的值 。 end。 end。 例題 ? 加分二叉樹（ noip2022） ? 【 問題描述 】 ? 設(shè)一個 n個節(jié)點(diǎn)的二叉樹 tree的中序遍歷為（ l,2,3,…,n ），其中數(shù)字1,2,3,…,n 為節(jié)點(diǎn)編號。每個節(jié)點(diǎn)都有一個分?jǐn)?shù)（均為正整數(shù)），記第 i個節(jié)點(diǎn)的分?jǐn)?shù)為 di， tree及它的每個子樹都有一個加分，任一棵子樹subtree（也包含 tree本身）的加分計算方法如下： ? subtree的左子樹的加分 subtree的右子樹的加分＋ subtree的根的分?jǐn)?shù) ? 若某個子樹為空，規(guī)定其加分為 1，葉子的加分就是葉節(jié)點(diǎn)本身的分?jǐn)?shù)。不考慮它的空子樹。 ? 試求一棵符合中序遍歷為（ 1,2,3,…,n ）且加分最高的二叉樹 tree。要求輸出； ? （ 1） tree的最高加分 ? （ 2） tree的前序遍歷 ? 【 輸入格式 】 ? 第 1行：一個整數(shù) n（ n＜ 30），為節(jié)點(diǎn)個數(shù)。 ? 第 2行： n個用空格隔開的整數(shù)，為每個節(jié)點(diǎn)的分?jǐn)?shù)（分?jǐn)?shù)＜ 100）。 ? 【 輸出格式 】 ? 第 1行：一個整數(shù)，為最高加分（結(jié)果不會超過 4,000,000,000）。 ? 第 2行： n個用空格隔開的整數(shù)，為該樹的前序遍歷。 ? 【 輸入樣例 】 ? 5 ? 5 7 1 2 10 ? 【 輸出樣例 】 ? 145 ? 3 1 2 4 5 ? 如果整棵樹的權(quán)值最大，必然有左子樹的權(quán)值最大，右子樹的權(quán)值也最大，符合最優(yōu)性原理 ? 本題適合用動態(tài)規(guī)劃來解。如果用數(shù)組 f[i,j]表示從節(jié)點(diǎn) i到節(jié)點(diǎn) j所組成的二叉樹的最大加分，枚舉根節(jié)點(diǎn)，則動態(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)。 ? var i:integer。 ? s:int64。 ? begin ? if f[l,r]0 then exit。//實(shí)現(xiàn)記憶化 ? if l=r then //處理邊界 ? begin ? f[l,r]:=a[l]。 ? d[l,r]:=l。 ? exit。 ? end。 ? for i:=l to r do ? begin ? s:=0。 ? if il0 then begin dfs(l,i1)。s:=f[l,i1]。end。//處理左子樹的加分 ? if ri0 then begin dfs(i+1,r)。if s0 then s:=s*f[i+1,r] else s:=f[i+1,r]。end。 ? inc(s,a[i])。 ? if sf[l,r] then ? begin f[l,r]:=s。 d[l,r]:=i。 end。 ? end。 ? end。 樹形動態(tài)規(guī)劃 ? 顧名思義，樹型動態(tài)規(guī)劃就是在“樹”的數(shù)據(jù)結(jié)構(gòu)上的動態(tài)規(guī)劃，平時作的動態(tài)規(guī)劃都是線性的或者是建立在圖上的，線性的動態(tài)規(guī)劃有二種方向既向前和向后，相應(yīng)的線性的動態(tài)規(guī)劃有二種方法既順推與逆推，而樹型動態(tài)規(guī)劃是建立在樹上的，所以也相應(yīng)的有二個方向： ? 根 — 葉：不過這種動態(tài)規(guī)劃在實(shí)際的問題中運(yùn)用的不多，也沒有比較明顯的例題，所以不在今天討論的范圍之內(nèi)。 ? 葉－ 根：既把根的子節(jié)點(diǎn)傳遞有用的信息給根，完成后根得出最優(yōu)解的過程。這類的習(xí)題比較的多，下面就介紹一些這類題目和它們的一般解法。（樹的后序遍歷求解） Ural 1018 二叉蘋果樹 ? 【 問題描述 】 ? 有一棵蘋果樹，如果樹枝有分叉，一定是分 2叉（就是說沒有只有 1個兒子的結(jié)點(diǎn)）這棵樹共有 N個結(jié)點(diǎn)（葉子點(diǎn)或者樹枝分叉點(diǎn)），編號為 1N,樹根編號一定是 1。 我們用一根樹枝兩端連接的結(jié)點(diǎn)的編號來描述一根樹枝的位置。下面是一顆有 4個樹枝的樹 2 5 \ / 3 4 \ / 1 現(xiàn)在這顆樹枝條太多了，需要剪枝。但是一些樹枝上長有蘋果。 給定需要保留的樹枝數(shù)量，求出最多能留住多少蘋果。 ? 輸入格式 ? 第 1行 2個數(shù)， N和 Q(1=Q= N,1N=100)。 N表示樹的結(jié)點(diǎn)數(shù)， Q表示要保留的樹枝數(shù)量。接下來 N1行描述樹枝的信息。 每行 3個整數(shù)，前兩個是它連接的結(jié)點(diǎn)的編號。第 3個數(shù)是這根樹枝上蘋果的數(shù)量。 每根樹枝上的蘋果不超過 30000個。 ? 輸出格式 ? 一個數(shù)，最多能留住的蘋果的數(shù)量。 ? 樣例輸入 ? 5 2 1 3 1 1 4 10 2 3 20 3 5 20 ? 樣例輸出 ? 21 ? 分析： ? 因?yàn)轭}目一給出就是純二叉的樹結(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]]。 （ 0=k=j1） ? 邊界： f[0,i]=0。f[i,0]=0。 ? 問題的解： f[1,q+1]。虛擬了一條邊，也就相當(dāng)于多添加了一個節(jié)點(diǎn) 1的父親節(jié)點(diǎn)，這條邊為 1和它父親節(jié)點(diǎn)的 ? procedure tree_dp(t,k:integer)。 ? var i,ls,rs:integer。 ? begin ? if f[t,k]0 then exit。 ? if (t=0) or (k=0) then ? begin ? f[t,k]:=0。 exit。 ? end。 ? f[t,k]:=0。 ? for i:=0 to k1 do ? begin ? tree_dp(tree[t].lc,i)。//左子樹 ? tree_dp(tree[t].rc,ki1)。//右子樹 ?
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1