【正文】 f[I,j]=max(f[i1,j],f[i1,j1]+a[j,i]) 區(qū)間類動態(tài)規(guī)劃 ? （ 1） 石子合并 ? 【 問題描述 】 ? 在一個圓形操場的四周擺放著 n 堆石子。 【 輸入樣例 】 4 4 4 9 5 ? 【 輸出樣例 】 43 54 ? 分析 ? 看到本題，容易想到使用貪心法，即每次選取相鄰最大或最小的兩堆石子合并。在項鏈上有 N顆能量珠。我們用記號 ⊕表示兩顆珠子的聚合操作， (j⊕ k)表示第 j， k兩顆珠子聚合后所釋放的能量。 【 輸出文件 】 輸出文件 ，是一個正整數(shù) E（ E≤*109），為一個最優(yōu)聚合順序所釋放的總能量。 ? 試求一棵符合中序遍歷為（ 1,2,3,…,n ）且加分最高的二叉樹 tree。 ? s:int64。s:=f[l,i1]。 end。下面是一顆有 4個樹枝的樹 2 5 \ / 3 4 \ / 1 現(xiàn)在這顆樹枝條太多了，需要剪枝。 每根樹枝上的蘋果不超過 30000個。 ? begin ? if f[t,k]0 then exit。//記錄左子樹的值 ? rs:=f[tree[t].rc,ki1]。 (1=N=200,1=M=150) ? 接下來的 N行 ,第 I+1行包含兩個整數(shù) ki和 si, ki表示第 I門課的直接先修課，si表示第 I門課的學(xué)分。 ? 其實是四種情況決策： (1) 選右子樹中 j門（ 2）選左子樹（ j1）門 +根 （ 3）選右子樹（ j1門） +根 （ 4）選左子樹（ k門） +根 +選右子樹（ jk1） ? 程序中節(jié)點－ 1表示空節(jié)點， 0是根節(jié)點， 1— n是n門可選課程的節(jié)點 . ? 源程序代碼： ? program bluewater。//狀態(tài)表示 ? f:array[0..200] of longint。 ? i:=b[a[x].l,k1]+b[a[x].r,yk]+a[x].k。 ? readln(n,m)。 ? if f[k]=0 then a[k].l:=i ? else a[f[k]].r:=i?，F(xiàn)在在整棵樹的根結(jié)點處已經(jīng)有了一個產(chǎn)品加工廠，而且所有的產(chǎn)品最終必須在某個加工廠加工才行。我們先利用兒子兄弟表示法，將多叉樹轉(zhuǎn)化為二叉樹 ? 進行了相關(guān)的轉(zhuǎn)化之后，設(shè) f(i,j,k)表示在新樹中，以 i結(jié)點為根的子樹中，分配 k個加工廠。,.(),(狀態(tài)壓縮動態(tài)規(guī)劃 ? 有一些問題卻被認為很可能不存在有效的(多項式級的 )算法，這里以對幾個例題的剖析，簡述狀態(tài)壓縮思想及其應(yīng)用。設(shè) fs為達到狀態(tài) s的方案數(shù)，則可以嘗試建立 f的遞推關(guān)系。 ? var n,i,t,c,j,tmp,r:longint。 ? for i:=1 to n do //讀入及預(yù)處理 ? begin ? a[i]:=0。 r:=0。 ? end。 本題狀態(tài)的 維數(shù)需要增加，原因在于并不是每一行只放一個棋子，也不是每一行都要求有棋子，原先的表示方法已經(jīng)無法完整表達一個狀態(tài)。 則狀態(tài)轉(zhuǎn)移方程很容易寫出 ： ? 同時我們可以用滾動數(shù)組優(yōu)化空間。 例題 ? 給出一個 n*m(n≤100,m≤10)的棋盤，一些格子不能放置棋子。 例題 ? 有 一個 n*m的棋盤 (n、 m≤80,n*m≤80)要在棋盤上放 k(k≤20)個棋子，使得任意兩個棋子不相鄰 (4個方向）。 ? tmp:=i and a[r]。 ? end。)。 ? 在 n*n(n≤20)的方格棋盤上放置 n個車，某些格子不能放，求使它們不能互相攻擊的方案總數(shù)。 分析 ? 我們?nèi)匀灰恍幸恍蟹胖谩? ?????????????處設(shè)廠處不設(shè)廠，ikkjr i g h t s o nifkil ef t s o nifijiD i siwkkjr i g h t s o nifkjl ef t s o nifkjif)139。而它到它的父結(jié)點的路徑的長度是 Ui。 ? {記憶化實現(xiàn)動規(guī) } ? treedp(a[0].l,m)。a[i].k:=1。 ? end。 ? treedp(a[x].r,y)。 ? i,j,k,l:longint。 ? 讀入數(shù)據(jù)時把二叉樹建好：第一個孩子作為父節(jié)點的左子樹，其它孩子作為第一個孩子的右子樹。 //保存最優(yōu)值 ? end。 ? f[t,k]:=0。f[i,0]=0。 N表示樹的結(jié)點數(shù)， Q表示要保留的樹枝數(shù)量。 ? 葉－ 根：既把根的子節(jié)點傳遞有用的信息給根，完成后根得出最優(yōu)解的過程。end。 ? exit。 ? 第 2行： n個用空格隔開的整數(shù)，為該樹的前序遍歷。 end。第二行是 N個用空格隔開的正整數(shù)，所有的數(shù)均不超過 1000。如果前一顆能量珠的頭標(biāo)記為 m，尾標(biāo)記為 r，后一顆能量珠的頭標(biāo)記為 r，尾標(biāo)記為 n，則聚合后釋放的能量為（ Mars單位），新產(chǎn)生的珠子的頭標(biāo)記為 m，尾標(biāo)記為 n。 ? 具體來說我們應(yīng)該定義一個數(shù)組 s[i,j]用來表示合并方法， i表示從編號為第 i堆的石頭開始合并，j表示從 i開始數(shù) j堆進行合并， s[i,j]為合并的最優(yōu)得分。 【 輸入文件 】 包含兩行，第 1 行是正整數(shù) n（ 1=n=100），表示有 n堆石子。 規(guī)劃方程為： （其中 A(i,j)是花束 i插在花瓶 j中的美學(xué)值） f[I,j]=max(f[i1,u]+a[I,j])(i=uj) 方法 2 以花瓶的數(shù)目來劃分階段。輸入整數(shù) F， V 和矩陣 (AIJ)，輸出最大美學(xué)值和每束花擺放在各個花瓶中的花瓶編號。 例題 【 問題描述 】 假設(shè)以最美觀的方式布置花店的櫥窗，有 F束花，每束花的品種都不一樣，同時，至少有同樣數(shù)量的花瓶，被按順序擺成一行，花瓶的位置是固定的，并從左到右，從 1到V順序編號， V 是花瓶的數(shù)目，編號為 1的花瓶在最左邊，編號為 V的花瓶在最右邊，花束可以移動，并且每束花用1到 F 的整數(shù)惟一標(biāo)識，標(biāo)識花束的整數(shù)決定了花束在花瓶中列的順序即如果 I J，則花束 I 必須放在花束 J左邊的花瓶中。 ? 狀態(tài)： f[I,j]表示，走到第 i行第 j列最大得分 ? 轉(zhuǎn)移： f[I,j]=f[i1,j1]+c[I,j](j1) ? =f[I1,j]+c[I,j](ji) For i := 2 to N Do For j := 1 to i Do Begin List[i, j].Tot := 1。 ? ●每一步可沿左斜線向下或右斜線向下走； ? ● 1＜三角形行數(shù) ≤100； ? ●三角形中的數(shù)字為整數(shù) 0， 1， …99 ； ? 輸入數(shù)據(jù)：