動態(tài)規(guī)劃程序設計5

1、安陽一中信息學奧賽輔導資料第1頁共6頁動態(tài)規(guī)劃程序設計動態(tài)規(guī)劃程序設計5區(qū)間型動態(tài)規(guī)劃在信息學競賽中應用甚廣，它是動態(tài)規(guī)劃中的經(jīng)典問題，最小代價字母樹是這類動態(tài)規(guī)劃最經(jīng)典的體現(xiàn)，對于初學者而言這類動態(tài)規(guī)劃并不太好理解。于是，區(qū)間型動態(tài)規(guī)劃又成了動態(tài)規(guī)劃中的難點問題。歷屆大賽中區(qū)間型動態(tài)規(guī)劃題目的考查。區(qū)間型動態(tài)規(guī)劃是各大信息學競賽出題的熱點，具體體現(xiàn)在以下題目：1合并石子——NOIl9952能量項鏈——NOIP20063加分二叉樹——N

2、OIP20034最優(yōu)排序二又樹——ctsc96這些題目出現(xiàn)的頻次及其所在比賽的重要性足以說明區(qū)間型動態(tài)規(guī)劃在各類動態(tài)規(guī)劃中有著舉足輕重的地位。區(qū)間類模型的動態(tài)規(guī)劃一般是要求整段區(qū)間的最優(yōu)值子問題一般是把區(qū)間分成兩個子區(qū)間。一般用二維數(shù)組表示狀態(tài)例如f[ij]表示從i到j的最優(yōu)值則狀態(tài)轉移方程就是跟子區(qū)間之間的關系。一、區(qū)間型動態(tài)規(guī)劃的算法分析一、區(qū)間型動態(tài)規(guī)劃的算法分析在這里就以經(jīng)典的最小代價字母樹作為例子，對區(qū)間型動態(tài)規(guī)劃的算法進行分

3、析。問題描述：給定一個序列，如4，1，2，3，我們將它們相加進行合并，最終合并成一個數(shù)，每次相加的代價是兩個加數(shù)的和，求怎樣的相加順序可以使總代價最小。很多初學者認為這類動態(tài)規(guī)劃不易理解，其重要原因是這類動態(tài)規(guī)劃與其他動態(tài)規(guī)劃的思想不大相同，而初學者又是利用其他動態(tài)規(guī)劃的思想來解決這類動態(tài)規(guī)劃，從而進入了思維誤區(qū)。這種錯誤的思維模式一旦建立便很難重新建立正確的解題思想，從而陷入絕境。這類動態(tài)規(guī)劃正確的解法是這樣的：首先，根據(jù)動態(tài)規(guī)劃無后

4、效性的性質(zhì)可以想到：對于一個序列：A1，A2…An，假如最后相加的兩個數(shù)是第一個數(shù)到第i個數(shù)的和s[1……i]以及第i1個數(shù)到第n個數(shù)的和s[i1…n]，另外，對于第一個數(shù)到第i個數(shù)相加的最小代價是F[l，i]以及從第i1到第n個數(shù)相加的最小代價為F[i1，n]，則總代價即為F[i1，n]F[1，i](前面相加的最小代價)s[1…i]s[i1…n](最后一次相加的最小代價)。由此，我們可以清楚地看出要想求出總代價的最小值只要枚舉i的位置

5、，使得F[i1，n]F[1，i]S[1i]s[i1…n]的和最小即可。綜上所述，我們可以總結出狀態(tài)轉移方程：F[i，J]：=rainF[i，k]F[k1，j]S[i，k]S[k1，j])狀態(tài)轉移數(shù)組F即代表從第i個數(shù)到第j個數(shù)相加的最小代價，s數(shù)組為預處理好的從第i個數(shù)到第j個數(shù)的和。核心代碼如下：Fi：=1tondoFj：=1tonIdoFk：=jtoij1doIff[jij]f[jk]f[k1Ij]s[jk]s[k1Ij]安陽一中信

6、息學奧賽輔導資料第3頁共6頁digui(xdg[xy])digui(dg[xy]y)ifbjthenbeginwrite(xdg[xy]y)bj:=falseendelsewrite(xdg[xy]y)endbeginreadln(n)fi:=1tondobeginread(S[i])endreadlnfill(fsizeof(f)$7f)fill(dgsizeof(dg)0)fi:=1tondof[ii1]:=0數(shù)據(jù)賦初值fjj:=2