【文章內(nèi)容簡(jiǎn)介】 后的 F行中，每行包含 V個(gè)整數(shù)， Aij 即為輸入文件中第（ i+1 ）行中的第 j個(gè)數(shù)。 輸出 輸出文件必須是名為 ，文件應(yīng)包含兩行： 第一行是程序所產(chǎn)生擺放方式的美學(xué)值。 第二行必須用 F個(gè)數(shù)表示擺放方式，即該行的第 K個(gè)數(shù)表示花束 K所在的花瓶的編號(hào)。 【 樣例輸入 】 3 5 7 23 –5 –24 16 5 21 4 10 23 21 5 4 20 20 【 樣例輸出 】 53 2 4 5 【 解法一 】 【 算法分析 】 問題實(shí)際就是給定 F束花和 V個(gè)花瓶，以及各束花放到不同花瓶中的美學(xué)值，要求你找出一種擺放的方案，使得在滿足編號(hào)小的花放進(jìn)編號(hào)小的花瓶中的條件下，美學(xué)值達(dá)到最大。 將問題進(jìn)行轉(zhuǎn)化，找出問題的原型。首先，看一下上述題目的樣例數(shù)據(jù)表格。 將擺放方案的要求用表格表現(xiàn)出來，則擺放方案需要滿足：每行選且只選一個(gè)數(shù)(花瓶 )；擺放方案的相鄰兩行中，下面一行的花瓶編號(hào)要大于上面一行的花瓶編號(hào)兩個(gè)條件。這時(shí)可將問題轉(zhuǎn)化為：給定一個(gè)數(shù)字表格，要求編程計(jì)算從頂行至底行的一條路徑，使得這條路徑所經(jīng)過的數(shù)字總和最大 (要求每行選且僅選一個(gè)數(shù)字 )。同時(shí)，路徑中相鄰兩行的數(shù)字，必須保證下一行數(shù)字的列數(shù)大于上一行數(shù)字的列數(shù)。 看到經(jīng)過轉(zhuǎn)化后的問題，發(fā)現(xiàn)問題與“數(shù)學(xué)三角形”問題十分相似，數(shù)字三角形問題的題意是： 給定一個(gè)數(shù)字三角形，要求編程計(jì)算從頂至底的一條路徑，使得路徑所經(jīng)過的數(shù)字總和最大 (要求每行選且僅選一個(gè)數(shù)字 )。同時(shí)，路徑中相鄰兩行的數(shù)字，必須保證下一行數(shù)字的列數(shù)與上一行數(shù)字的列數(shù)相等或者等于上一行數(shù)字的列數(shù)加 1。 上例中已經(jīng)知道：數(shù)字三角形中的經(jīng)過數(shù)字之和最大的最佳路徑，路徑的每個(gè)中間點(diǎn)到最底層的路徑必然也是最優(yōu)的，可以用動(dòng)態(tài)規(guī)劃方法求解，對(duì)于“花店櫥窗布置”問題經(jīng)過轉(zhuǎn)化后，也可采取同樣的方法得出本題同樣符合最優(yōu)性原理。因此，可以對(duì)此題采用動(dòng)態(tài)規(guī)劃的方法。 ? 【 參考程序 】 ? includeiostream ? includecstring ? includecstdio ? using namespace std。 ? int main() ? { ? int a[101][101],b[101][101],c[101][101],d[101]。 //a[i][j] 花束 i放在花瓶 j中的美學(xué)值 ? //b[i][j] 前 i束花放在前 j個(gè)花瓶中的最優(yōu)解 ? //c[i][j] 在 b[i][j]的最優(yōu)解中，花束 i1的位置 ? int f,v,i,j,k,max。 //f , v 花束和花瓶的數(shù)目 ? cinfv。 ? for (i=1。i=f。i++) ? for (j=1。j=v。j++) ? cina[i][j]。 ? memset(b,128,sizeof(b))。 //這樣處理，可以保證每束花都放進(jìn)花瓶 ? for (i=1。i=vf+1。i++) //初始化第 1束花放在第 i個(gè)花瓶的情況 ? b[1][i]=a[1][i]。 ? for (i=2。i=f。i++) ? for (j=i。j=vf+i。j++) ? for (k=i1。k=j1。k++) //枚舉花束 i1的位置 ? if (b[i1][k]+a[i][j]b[i][j]) ? { ? b[i][j]=b[i1][k]+a[i][j]。 //更新當(dāng)前最優(yōu)解 ? c[i][j]=k。 //前一個(gè)花束的位置為 k ? } max=2100000000。 for (i=f。i=v。i++) if (b[f][i]max) { max=b[f][i]。 //選擇全局最優(yōu)解 k=i。 //k最后一束花的位置 } coutmaxendl。 //打印最優(yōu)解 for (i=1。i=f。i++) { d[i]=k。 k=c[fi+1][k]。 } for (i=f。i=2。i) coutd[i] 。 coutd[1]endl。 } 由此可看出，對(duì)于看似復(fù)雜的問題，通過轉(zhuǎn)化就可變成簡(jiǎn)單的經(jīng)典的動(dòng)態(tài)規(guī)劃問題。在問題原型的基礎(chǔ)上，通過分析新問題與原問題的不同之處，修改狀態(tài)轉(zhuǎn)移方程，改變問題狀態(tài)的描述和表示方式，就會(huì)降低問題規(guī)劃和實(shí)現(xiàn)的難度，提高算法的效率。由此可見，動(dòng)態(tài)規(guī)劃問題中具體的規(guī)劃方法將直接決定解決問題的難易程度和算法的時(shí)間與空間效率，而注意在具體的規(guī)劃過程中的靈活性和技巧性將是動(dòng)態(tài)規(guī)劃方法提出的更高要求。 【 解法二 】 【 算法分析 】 flower一題是 IOI99第一天第一題，該題如用組合的方法處理，將會(huì)造成超時(shí)。正確的方法是用動(dòng)態(tài)規(guī)劃，考慮角度為一束一束地增加花束，假設(shè)用 b[i][j]表示 1～ i束花放在 1到 j之間的花瓶中的最大美學(xué)值，其中 i=j ，則b[i][j]=max(b[i1][k1]+A[i][k])，其中 i=k=j， A[i][k]的含義參見題目。輸出結(jié)果時(shí)，顯然使得 b[F][k]取得總的最大美觀值的第一個(gè) k值就是第 F束花應(yīng)該擺放的花瓶位置，將總的最大美觀值減去 A[i][k]的值即得到前 k1束花放在前 k1個(gè)瓶中的最大美觀值，依次使用同樣的方法就可求出每一束花應(yīng)該擺放的花瓶號(hào)。由于這一過程是倒推出來的，所以程序中用遞歸程序來實(shí)現(xiàn)。 【 參考程序 】 includeiostream includecstdio includecstring using namespace std。 void print(int,int)。 int max(int a,int b) { return ab?a:b。 } int a[101][101],b[101][101]。 int main() { int f,v。 cinfv。 for (int i=1。i=f。i++) for (int j=1。j=v。j++) cina[i][j]。 memset(b,128,sizeof(b))。 //初始化 b數(shù)組 for (int i=0。i101。i++) b[0][i]=0。 //沒有放花時(shí)，美學(xué)值為 0。這也是初始化 for (int i=1。i=f。i++) for (int j=i。j=vf+i。j++) { for (int k=i。k=j。k++) b[i][j]=max(b[i][j],b[i1][k1]+a[i][k])。 } int c=1000000。 for (int i=f。i=v。i++) if (b[f][i]c) c=b[f][i]。 coutcendl。 print(f,c)。 } void print(int i,int j) { int n。 if (i0) { n=i。 while (b[i][n]!=j) { n++。 } print(i1,ja[i][n])。 coutn 。 } } 記憶化搜索的應(yīng)用 一般來說，動(dòng)態(tài)規(guī)劃總要遍歷所有的狀態(tài)，而搜索可以排除一些無效狀態(tài)。更重要的是搜索還可以剪枝，可能剪去大量不必要的狀態(tài)，因此在空間開銷上往往比動(dòng)態(tài)規(guī)劃要低很多。 如何協(xié)調(diào)好動(dòng)態(tài)規(guī)劃的高效率與高消費(fèi)之間的矛盾呢？有一種折中的辦法就是記憶化算法。記憶化算法在求解的時(shí)候還是按著自頂向下的順序，每求解一個(gè)狀態(tài)，就將它的解保存下來，以后再次遇到這個(gè)狀態(tài)的時(shí)候，就不必重新求解了。這種方法綜合了搜索和動(dòng)態(tài)規(guī)劃兩方面的優(yōu)點(diǎn)，因而還是很有使用價(jià)值的。舉一個(gè)例子：如下圖所示是一個(gè)有向無環(huán)圖，求從頂點(diǎn) 1到頂點(diǎn) 6的最長路徑。（規(guī)定邊的方向從左到右） 我們將從起點(diǎn)（頂點(diǎn) 1）開始到某個(gè)頂點(diǎn)的最長路徑作為狀態(tài)，用一維數(shù)組 opt記錄。 Opt[j]表示由起點(diǎn)到頂點(diǎn) j時(shí)的最長路徑。顯然， opt[1]=0，這是初始狀態(tài)，即動(dòng)態(tài)規(guī)劃的邊界條件。于是，我們很容易地寫出狀態(tài)轉(zhuǎn)移方程式： opt[j]=max{opt[k]+a[k][j]}（ k到 j有一條長度為 a[k][j]的邊）。雖然有了完整的狀態(tài)轉(zhuǎn)移方程式，但是還是不知道動(dòng)態(tài)規(guī)劃的順序。所以，還需要先進(jìn)行一下拓?fù)渑判颍凑张判虻捻樞蛲葡氯ィ?opt[6]就是問題的解。 可以看出，動(dòng)態(tài)規(guī)劃相比搜索之所以高效，是因?yàn)樗鼘⑺械臓顟B(tài)都保存了下來。當(dāng)遇到重復(fù)子問題時(shí)，它不像搜索那樣把這個(gè)狀態(tài)的最優(yōu)值再計(jì)算一遍，只要把那個(gè)狀態(tài)的最優(yōu)值調(diào)出來就可以了。例如，當(dāng)計(jì)算 opt[4]和 opt[5]時(shí)，都用到了 opt[3]的值。因?yàn)橐呀?jīng)將它保存下來了，所以就沒有必要再去搜索了。 但是動(dòng)態(tài)規(guī)劃仍然是有缺點(diǎn)的。一個(gè)很突出的缺點(diǎn)就是要進(jìn)行拓?fù)渑判?。這道題的拓?fù)潢P(guān)系是很簡(jiǎn)單的，但有些題的拓?fù)潢P(guān)系是很復(fù)雜的。對(duì)于這些題目，如果也進(jìn)行拓?fù)渑判?，工作量非常大。遇到這種情況，我們可以用記憶化搜索的方法，避免拓?fù)渑判颉? 【 例 924】 滑雪 【 問題描述 】 小明喜歡滑雪，因?yàn)榛┑拇_很刺激，可是為了獲得速度，滑的區(qū)域必須向下傾斜，當(dāng)小明滑到坡底，不得不再次走上坡或等著直升機(jī)來載他，小明想知道在一個(gè)區(qū)域中最長的滑坡?；碌拈L度由滑過點(diǎn)的個(gè)數(shù)來計(jì)算，區(qū)域由一個(gè)二維數(shù)組給出，數(shù)組的每個(gè)數(shù)字代表點(diǎn)的高度。下面是一個(gè)例子： 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9 一個(gè)人可以從某個(gè)點(diǎn)滑向上下左右相鄰四個(gè)點(diǎn)之一，當(dāng)且僅當(dāng)高度減小，在上面的例子中，一條可行的滑坡為 252417161（從 25開始到 1結(jié)束），當(dāng)然2524……2…1 更長，事實(shí)上這是最長的一條。 【 輸入格式 】 輸入的第一行為表示區(qū)域的二維數(shù)組的行數(shù) R和列數(shù) C（ 1≤R、 C≤100）下面是 R行，每行有 C個(gè)數(shù)代表高度。 【 輸出格式 】 輸出區(qū)域中最長的滑坡長度。 [i1,j]↓ [i,j1]→ [i,j] ←[i,j+1] [i+1,j]↑ 【 輸入樣例 】