動(dòng)態(tài)規(guī)劃及其應(yīng)用-文庫吧資料
2024-08-18 03:45本頁面
【正文】 ? ls:=f[tree[t].lc,i]。 ? for i:=0 to k1 do ? begin ? tree_dp(tree[t].lc,i)。 ? end。 ? if (t=0) or (k=0) then ? begin ? f[t,k]:=0。 ? var i,ls,rs:integer。 ? 問題的解： f[1,q+1]。 （ 0=k=j1） ? 邊界： f[0,i]=0。 ? 輸出格式 ? 一個(gè)數(shù)，最多能留住的蘋果的數(shù)量。第 3個(gè)數(shù)是這根樹枝上蘋果的數(shù)量。接下來 N1行描述樹枝的信息。 ? 輸入格式 ? 第 1行 2個(gè)數(shù)， N和 Q(1=Q= N,1N=100)。但是一些樹枝上長有蘋果。 我們用一根樹枝兩端連接的結(jié)點(diǎn)的編號來描述一根樹枝的位置。這類的習(xí)題比較的多，下面就介紹一些這類題目和它們的一般解法。 樹形動(dòng)態(tài)規(guī)劃 ? 顧名思義，樹型動(dòng)態(tài)規(guī)劃就是在“樹”的數(shù)據(jù)結(jié)構(gòu)上的動(dòng)態(tài)規(guī)劃，平時(shí)作的動(dòng)態(tài)規(guī)劃都是線性的或者是建立在圖上的，線性的動(dòng)態(tài)規(guī)劃有二種方向既向前和向后，相應(yīng)的線性的動(dòng)態(tài)規(guī)劃有二種方法既順推與逆推，而樹型動(dòng)態(tài)規(guī)劃是建立在樹上的，所以也相應(yīng)的有二個(gè)方向： ? 根 — 葉：不過這種動(dòng)態(tài)規(guī)劃在實(shí)際的問題中運(yùn)用的不多，也沒有比較明顯的例題，所以不在今天討論的范圍之內(nèi)。 ? end。 d[l,r]:=i。 ? inc(s,a[i])。if s0 then s:=s*f[i+1,r] else s:=f[i+1,r]。end。 ? if il0 then begin dfs(l,i1)。 ? end。 ? d[l,r]:=l。 ? begin ? if f[l,r]0 then exit。 ? var i:integer。 ? 【 輸入樣例 】 ? 5 ? 5 7 1 2 10 ? 【 輸出樣例 】 ? 145 ? 3 1 2 4 5 ? 如果整棵樹的權(quán)值最大，必然有左子樹的權(quán)值最大，右子樹的權(quán)值也最大，符合最優(yōu)性原理 ? 本題適合用動(dòng)態(tài)規(guī)劃來解。 ? 【 輸出格式 】 ? 第 1行：一個(gè)整數(shù)，為最高加分（結(jié)果不會(huì)超過 4,000,000,000）。要求輸出； ? （ 1） tree的最高加分 ? （ 2） tree的前序遍歷 ? 【 輸入格式 】 ? 第 1行：一個(gè)整數(shù) n（ n＜ 30），為節(jié)點(diǎn)個(gè)數(shù)。不考慮它的空子樹。 例題 ? 加分二叉樹（ noip2022） ? 【 問題描述 】 ? 設(shè)一個(gè) n個(gè)節(jié)點(diǎn)的二叉樹 tree的中序遍歷為（ l,2,3,…,n ），其中數(shù)字1,2,3,…,n 為節(jié)點(diǎn)編號。 end。 【 輸入樣例 】 4 2 3 5 10 【 輸出樣例 】 710 算法分析 ? 如果要求一個(gè)鏈的最優(yōu)合并方式 ,可以把這個(gè)鏈從中間斷開 ,枚舉斷開處 ,分別求出 2段的最優(yōu)合并的值 ,再將這兩端合并 ,而這條鏈斷開后的 2段的最優(yōu)合并方式也可以用同樣的方式計(jì)算 ,因此 ,本題具有最優(yōu)子結(jié)構(gòu)性質(zhì) ,可以用動(dòng)態(tài)規(guī)劃求解 ? 但本題中并不是一個(gè)鏈而是一個(gè)環(huán) ,但這并不影響最優(yōu)子結(jié)構(gòu)性質(zhì) ,可以做一條鏈 ,長度是環(huán)的 2倍 ,其中前半段與后半段一樣 ,都為環(huán)的順序 (可任意確定 ),那么 ,從中間任取長度為 n的一段 ,就實(shí)現(xiàn)了環(huán)的性質(zhì) 首尾相接 ? 設(shè) f[k,j]為從珠子 k到珠子 j的最優(yōu)合并 ,那么枚舉斷開點(diǎn) p, 則 f[k,j]的最優(yōu)值為 f[k,p]的最優(yōu)值和 f[p+1,j]的最優(yōu)值的和再加珠子 [k,p]和 [p+1,j]合并的值 v[k](k的頭標(biāo)記 )*v[p+1](p的尾標(biāo)記 =p+1的頭標(biāo)記 )*v[j+1](即 j的尾標(biāo)記 ) ? 動(dòng)規(guī)方程為 :f[k,j]=max{f[k,p]+f[p+1,j]+v[k]*v[p+1]*v[j+1]} (kj2*n且 k=pj) ? for d=1 to n //從小到大枚舉鏈的長度 for k=1 to 2*n do //枚舉鏈的起點(diǎn) begin j=k+d1。 至于珠子的順序，你可以這樣確定：將項(xiàng)鏈放到桌面上，不要出現(xiàn)交叉，隨意指定第一顆珠子，然后按順時(shí)針方向確定其他珠子的順序。第 i個(gè)數(shù)為第 i顆珠子的頭標(biāo)記（ 1≤i≤N），當(dāng) iN span時(shí)，第 i顆珠子的尾標(biāo)記應(yīng)該等于第 i+1顆珠子的頭標(biāo)記。 ? 【 輸入文件 】 輸入文件 N（ 4≤N≤100），表示項(xiàng)鏈上珠子的個(gè)數(shù)。則第 1兩顆珠子聚合后釋放的能量為： (4⊕ 1)=10*2*3=60。 例如：設(shè) N=4， 4顆珠子的頭標(biāo)記與尾標(biāo)記依次為 (2， 3) (3， 5) (5， 10) (10， 2)。 需要時(shí)， Mars人就用吸盤夾住相鄰的兩顆珠子，通過聚合得到能量，直到項(xiàng)鏈上只剩下一顆珠子為止。因?yàn)橹挥羞@樣，通過吸盤（吸盤是 Mars人吸收能量的一種器官）的作用，這兩顆珠子才能聚合成一顆珠子，同時(shí)釋放出可以被吸盤吸收的能量。能量珠是一顆有頭標(biāo)記與尾標(biāo)記的珠子，這些標(biāo)記對應(yīng)著某個(gè)正整數(shù)。 ? 在 Mars星球上，每個(gè) Mars人都隨身佩帶著一串能量項(xiàng)鏈。 ? 則動(dòng)規(guī)方程為： ? S[I,j]=min{s[I,k]+s[i+k,jk]+sum[I,j]} ? 1=k=j1 ? 2=j=n ? 邊界： s[I,1]=0。 ? 為什么？ ? 顯然，貪心只能導(dǎo)致局部的最優(yōu)，而局部最優(yōu)并不導(dǎo)致全局最優(yōu)。 ? 然而這樣做對不對呢？看一個(gè)例子。 第 1 行中的數(shù)是最小得分；第 2 行中的數(shù)是最大得分。 第 2行有 n個(gè)數(shù)，分別表示每堆石子的個(gè)數(shù)。 試設(shè)計(jì)一個(gè)算法，計(jì)算出將 n堆石子合并成一堆的最小得分和最大得分?，F(xiàn)要 將 石子有次序地合并成一堆。最優(yōu)指標(biāo)函數(shù) fk(sk)表示前 k個(gè)花瓶中插了 sk束花，所能取得的最大美學(xué)值。在這里階段變量 k表示的是要占用的花瓶數(shù)目（前 k個(gè)花瓶），狀態(tài)變量 sk表示前 k個(gè)花瓶中放了多少花。最優(yōu)指標(biāo)函數(shù) fk(sk)表示前 k束花，其中第 k束插在第 sk個(gè)花瓶中，所能取得的最大美學(xué)值。在這里，階段變量 k表示的就是要布置的花束數(shù)目（前 k束花），狀態(tài)變量 sk表示第 k束花所在的花瓶。第二行必須用 F 個(gè)數(shù)表示擺放方式，即該行的第 K個(gè)數(shù)表示花束 K所在的花瓶的編號。 ? 【 輸入文件 】 ? 第一行包含兩個(gè)數(shù)： F， V。題中數(shù)據(jù)滿足下面條件： 1≤F≤100， F≤V≤100，－50≤AIJ≤50，其中 AII是花束 I擺放在花瓶 J中的美學(xué)值。比如杜鵑花放在花瓶 2中，會(huì)顯得非常好看，但若放在花瓶 4中則顯得很難看。 每一個(gè)花瓶的形狀和顏色也不相同，因此，當(dāng)各個(gè)花瓶中放入不同的花束時(shí)會(huì)產(chǎn)
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1