南開大學ACM暑期集訓之動態(tài)規(guī)劃ppt課件

1、南開大學ACM暑期集訓之動態(tài)規(guī)劃朱毅2006年8月本講稿主要來源福州大學數(shù)學與計算機科學學院第一節(jié)動態(tài)規(guī)劃的根本要素 動態(tài)規(guī)劃主要用于組合優(yōu)化問題，即求一個離散問題在某種意義下的最優(yōu)解，有時也用于組合計數(shù)問題。 那么，什么樣的問題適宜用動態(tài)規(guī)劃求解呢? 適宜用動態(tài)規(guī)劃求解的問題的兩個根本要素: (1)最優(yōu)子構造性質(zhì) 一個問題可用動態(tài)規(guī)劃有效求解的根本要求是該問題具有最優(yōu)子構造性質(zhì)，通俗地講即問題的最優(yōu)解包含其子問題的最優(yōu)解。 (2)子問題重疊性質(zhì) 動態(tài)規(guī)劃所針對的問題還有另外一個顯著的特征，即它所對應的子問題樹中的子問題呈現(xiàn)大量的反復，稱為子問題重疊性質(zhì)。 在運用動態(tài)規(guī)劃時，對于反復出現(xiàn)的子問

2、題，只需在第一次遇到時加以求解，并把答案保管起來，以便以后再遇到時直接援用，不用重新求解，從而大大地提高解題的效率。 相比之下，普通的搜索技術，對于某個子問題，不論能否曾經(jīng)求解過，只需遇上，就會再次對它求解，因此影響了解題的效率。實例一、數(shù)字三角形問題 1問題描畫 給定一個具有N層的數(shù)字三角形，從頂至底有多條途徑，每一步可沿左斜線向下或沿右斜線向下，途徑所經(jīng)過的數(shù)字之和為途徑得分，懇求出最小途徑得分。 2 6 2 1 8 4 1 5 6 8圖41 數(shù)字三角形 2解題思緒 這道題可以用動態(tài)規(guī)劃勝利地處理，但是，假設對問題的最優(yōu)構造描寫得不恰當(即形狀表示不適宜)，那么無法運用動態(tài)規(guī)劃。 形狀表示

3、法一： 用一元組D(X)描畫問題，D(X)表示從頂層到達第X層的最小途徑得分。因此，此問題就是求出D(N)(假設需求，還應求出最優(yōu)途徑)。這是一種很自然的想法和表示方法。遺憾的是，這種描畫方式并不能滿足最優(yōu)子構造性質(zhì)。由于D(X)的最優(yōu)解(即最優(yōu)途徑)能夠不包含子問題例如D(X-1)的最優(yōu)解。如圖41所示： 顯然，D(4)2+6+1+110，其最優(yōu)解(途徑)為2-6-1-1。而D(3)2+2+48，最優(yōu)解(途徑)為2-2-4。故D(4)的最優(yōu)解不包含子問題D(3)的最優(yōu)解。由于不滿足最優(yōu)子構造性質(zhì)，因此無法建立子問題最優(yōu)值之間的遞歸關系，也即無法運用動態(tài)規(guī)劃。 2 6 2 1 8 4 1 5

4、6 8圖41 數(shù)字三角形 形狀表示法二： 用二元組D(X,y)描畫問題，D(X,y)表示從頂層到達第X層第y個位置的最小途徑得分。 最優(yōu)子構造性質(zhì)：容易看出，D(X,y)的最優(yōu)途徑Path(X,y)一定包含子問題D(X-1,y)或D(X-1,y-1)的最優(yōu)途徑。 否那么，取D(X-1,y)和D(X-l,y-1)的最優(yōu)途徑中得分小的那條途徑加上第X層第y個位置構成的途徑得分必然小于Path(X,y)的得分，這與Path(X,y)的最優(yōu)性是矛盾的。 2 6 2 1 8 4 1 5 6 8圖41 數(shù)字三角形 n 如圖41所示，D(4,2)的最優(yōu)途徑為2-6-1-5，它包含D(3,1)最優(yōu)途徑2-6-

5、1。因此，用二元組D(X,y)描畫的計算D(X,y)的問題具有最優(yōu)子構造性質(zhì)。 遞歸關系： D(X,y)minD(X-1,y)，D(X-1,y-1+a(X,y) D(1,1)a(1,1) n其中，a(X,y)為第X層第y個位置的數(shù)值。n 原問題的最小途徑得分可以經(jīng)過比較D(N,i)獲得，其中i1，2，N。n 在上述遞歸關系中，求D(X,y)的時候，先計算D(X-1,y)和D(X-1,y-1)，下一步求D(X，y+1)時需求D(X-1，y+1)和D(X-1，y)，但其中D(X-1，y)在前面曾經(jīng)計算過了。于是，子問題重疊性質(zhì)成立。n 因此，采用形狀表示法二描畫的問題具備了用動態(tài)規(guī)劃求解的根本要素

6、，可以用動態(tài)規(guī)劃進展求解。 形狀表示法三： 采用形狀表示法二的方法是從頂層開場，逐漸向下至底層來求出原問題的解。現(xiàn)實上，還可以從相反的方向思索。仍用二元組D(X,y)描畫問題，D(X,y)表示從第X層第y個位置到達底層的最小途徑得分。原問題的最小途徑得分即為D(1,1)。 最優(yōu)子構造性質(zhì)：顯然，D(X,y)的最優(yōu)途徑Path(X,y)一定包含子問題D(X+1,y)或D(X+1,y+1)的最優(yōu)途徑，否那么，取D(X+1,y)和D(X+1,y+1)的最優(yōu)途徑中得分小的那條途徑加上第X層第y個位置構成的途徑得分必然小于Path(X,y)的得分，這與Path(X,y)的最優(yōu)性矛盾。 2 6 2 1 8

7、 4 1 5 6 8圖41 數(shù)字三角形 n 如下圖，D(1，1)的最優(yōu)途徑為2-6-1-1，它包含D(2,1)的最優(yōu)途徑6-1-1。因此，這種形狀表示描畫的計算D(X，y)的問題同樣具有最優(yōu)子構造性質(zhì)。n遞歸關系：n D(X,y)minD(X+1,y),D(X+1,y+1)+a(X,y)n D(N,k)a(N,k)，k1，Nn其中，a(X，y)為第X層第y個位置的數(shù)值。n D(X,y)表示從第X層第y個位置到達底層的最小途徑得分。原問題的最小途徑得分即為D(1,1)。 算法設計 采用形狀表示法三的算法的主要過程如下： for ( i = n - 2; i = 0; -i ) for ( j =

8、 0; j = i; +j )tmp = soui + 1j;if ( soui + 1j + 1 tmp )tmp = soui + 1j + 1;souij += tmp; printf( %dn, sou00 );第二節(jié)動態(tài)規(guī)劃算法步驟 (1)選擇適當?shù)膯栴}形狀表示，并分析最優(yōu)解的性質(zhì)； (2)遞歸地定義最優(yōu)值(即建立遞歸關系)； (3)以自底向上的方式計算出最優(yōu)值； (4)根據(jù)計算最優(yōu)值時得到的信息，構造一個最優(yōu)解。 步驟(1)(3)是動態(tài)規(guī)劃的根本步驟。在只需求求出最優(yōu)值的情形，步驟(4)可以省略。 假設需求求出問題的一個最優(yōu)解，那么必需執(zhí)行步驟(4)。此時，在步驟(3)中計算最優(yōu)值

9、時，通常需記錄更多的信息，以便在步驟(4)中，根據(jù)所記錄的信息，快速地構造出一個最優(yōu)解。 本卷須知: 在進一步討論動態(tài)規(guī)劃設計方法及運用之前，有兩點需求留意： (1)問題的形狀表示對能否用動態(tài)規(guī)劃進展求解是至關重要的，不恰當?shù)男螤畋硎緦⑹箚栴}的描畫不具有最優(yōu)子構造性質(zhì)，從而無法建立最優(yōu)值的遞歸關系，動態(tài)規(guī)劃的運用也就無從談起。因此，上面步驟(1)，即形狀表示和最優(yōu)子構造性質(zhì)的分析，是最關鍵的一步。 (2)在算法的程序設計中，應充分利用子問題重疊性質(zhì)來提高解題效率。更詳細地說，應采用遞推(迭代)的方法來編程計算由遞歸式定義的最優(yōu)值，而不采用直接遞歸的方法。實例二、花束擺放問題 1問題描畫 如今有

10、F束不同種類的花束，同時有至少同樣數(shù)量的花瓶被按順序擺成一行，其位置固定于架子上，并從1至V按從左到右順序編號，V是花瓶的數(shù)目(FV)?；ㄊ梢耘矂?，并且每束花用1至F的整數(shù)獨一標識。標識花束的整數(shù)決議了花束在花瓶中陳列的順序，假設ij，花束i必需放在花束j左邊的花瓶中。每個花瓶只能放一束花。假設花瓶的數(shù)目大于花束的數(shù)目，那么多余的花瓶空置。 每一個花瓶都具有各自的特點。因此，當各個花瓶中放入不同的花束時，會產(chǎn)生不同的美學效果，并以一美學值(一個整數(shù))來表示，空置花瓶的美學值為零。為獲得最正確美學效果，必需在堅持花束順序的前提下，使花束的擺放獲得最大的美學值。懇求出具有最大美學值的一種擺放方式

11、。 2解題思緒 形狀表示法一： 設A(i,j)表示第i種花束擺在第j個花瓶中獲得的美學值。S(i,k)表示第i種花束擺在第k個花瓶中時(這里ki)，前i種花束可以獲得的最大美學值(之和)。這樣，原問題的最優(yōu)值可以經(jīng)過計算maxS(F,k)FkV獲得。 下面要分析一下這種形狀表示法描畫問題的方式能否具備了用動態(tài)規(guī)劃求解的根本要素。 最優(yōu)子構造性質(zhì)：對滿足FkV的k，設T(F,k)是到達最優(yōu)值S(F,k)的一種最正確擺放方式，其中，第F-1種花束擺在第j個花瓶中(j1 S(1,k)=A(1,k) 在計算S(i,k-1)時，曾經(jīng)計算出了S(i-1,j)，i-1jk-2及其 maxS(i-1,j)i-

12、1jk-2 。因此，計算S(i,k)時，只需將S(i-1,k-1)與max S(i-1,j)i-1jk-2 進展比較即可求得,即子問題重疊性質(zhì)。這樣做可以大大減少計算量。 現(xiàn)實上，還可以有更直接的方法。 形狀表示法二： 設Si,k表示第i種花束擺在第k個之前(包括第k個)的恣意某個花瓶中，前i種花束可以獲得的最大美學值(之和)。這樣，原問題的最優(yōu)值即為SF,V。這比前一個表示法更直接。 容易驗證，計算SF,V的問題具有最優(yōu)子構造性質(zhì)。 其遞歸方程為： Si,k=maxSi-1,k-1+A(i,k)，Si,k-1，(i1，ki); 初始條件為： S1,1=A1,1; S1,k=maxA(1,k)

13、,S1,k-1，(k1); Si,i=Si-1,i-1+A(i,i)， (i1) 算法設計(形狀表示法二) 算法的過程如下： s00 = a00; out00 = true; for ( j = 1; j a0j ? s0j - 1 :a0j;out0j = ( s0j != s0j - 1 );for ( i = 1; i f & i ?= si - 1j - 1 + aij;outij = ( sij != sij - 1 );sij = si - 1j - 1 + aij; outij = true;if ( i ?= sij - 1; outij = ( sij != sij

14、- 1 ); 實例三、美觀輸出問題 1問題描畫 給定N個英文單詞組成的一段文章，每個單詞的長度(字符個數(shù))依序為l1, l2,ln ，要在一臺每行最多能打印M( li M，i1,2,n )個字符的打印機上將這段文章“美觀地輸出來。這里的“美觀指的是：在打印機輸出的每一行中，行首和行尾可以不留空格，行中每兩個單詞之間留一個空格。且不允許將單詞拆開。除文章的最后一行外，希望每行多余的空格數(shù)的總和盡能夠少，同時多余的空格數(shù)在每行的分布盡能夠均勻，為此，把每行的多余空格數(shù)(除最后一行外)的平方和到達最小作為“美觀的規(guī)范。懇求出個“美觀的輸出方案。 2解題思緒 由上面的分析很自然想到采用這樣一種戰(zhàn)略(稱

15、為貪婪戰(zhàn)略)：每一行在不突破單詞的前提下按順序盡能夠多地輸出單詞。 但是，這樣做法有時無法求得最優(yōu)解。 例如，對n5, l142, l25, l320, l420, l540, M50，根據(jù)該戰(zhàn)略得到的輸出方案是1,2,3,4,5，但這不是最優(yōu)輸出方案，其多余空格數(shù)(除最后一行外)的平方和為22 + 92 85?，F(xiàn)實上，輸出方案1,2,3,4,5為最優(yōu)輸出方案，其多余空格數(shù)(除最后一行外)的平方和為82 + 32 73。 為此，思索用動態(tài)規(guī)劃求解。設C1,k是安排單詞1k時的最小費用 ， 那 么 所 要 求 的 最 小 費 用 為C1,n。 討論： C1,k具有最優(yōu)子構造性質(zhì)？ 答案能否認的。

16、n為此我們思索 Ck,n。n設Ck,n,(k1)是從一行開場安排單詞kn時的最小費用，那么所要求的最小費用為C1,n。n (1)問題具有最優(yōu)子構造性質(zhì)：在一個最優(yōu)輸出方案中，從行頭開場的子輸出方案是子問題的最優(yōu)輸出方案。 (2)建立遞歸關系 設 Si,j= M-(j-i)-n Si,j0nfeei,j= 0 Si,j0,j=nn (Si,j)2,其它情況n為將單詞ij安排在一行輸出時行尾的空格數(shù)。需求留意的是， Si,j能夠為負。n feei,j表示將單詞ij打印在一行上的費用，那么 jikkl遞歸關系：Ck,n,(1kn)是從一行開場安排單詞kn時的最小費用，所要求的最小費用為C1,n。 C

17、 k, n = (k=1,2,n)C n+1, n = 0 (n 1) , 1,minnjCjkfeenjk實例四、排隊買票問題 1問題描畫 一場演唱會即將舉行?，F(xiàn)有n個歌迷排隊買演唱會的票。一個人1張票。第i位歌迷買l張票需求時間t(i),為加快售票過程，售票處規(guī)定，隊伍中相鄰的2位歌迷(第j人和第j+1人)也可以由其中一人(例如第j位)買2張票(一個人每次最多也只能買2張票)，而另外一位就不用排隊了(也不再替他人買票)，按這種方式買票，這2位歌迷買2張票的時間變?yōu)閞(j) 。給出n，t(i)和r(j)的值，編程求出使每個人都買到一張票的最短時間和方法。 2解題思緒 此題可以用深度優(yōu)先搜索來

18、求解，但其時間復雜度為指數(shù)增長，因此思索能否用動態(tài)規(guī)劃的方法。 形狀表示：以f(i)表示第i位和其后的歌迷總的買票時間的最小值，但不委托第i-1位歌迷買票?？偟馁I票時間的最小值為f(1)。 最優(yōu)子構造性質(zhì)：假設i1i2ik，kn是l，n的一個最正確買票方法，其中ip，lp k 表示第p個買票的是隊伍中排在第ip個的歌迷。 如今，無非有3種情況： (1)第1位歌迷只為本人買票，即i1=1。顯然， i2ik，kn是2，n的一個最正確買票方法。 (2)第1位歌迷委托第2位歌迷買票，即i1=2。此時，i2ik，kn是3，n的一個最正確買票方法。 (3)第1位歌迷替第2位歌迷買票，即i1=1。此時，i2

19、ik，kn仍是3，n的一個最正確買票方法。 因此，問題具有最優(yōu)子構造性質(zhì)。根據(jù)該性質(zhì)，容易得到形狀轉(zhuǎn)移方程： 遞歸關系： f(i)= mint(i)+f(i+1),minr(i),r(i+1)+f(i+2) (i=1,2,n-1)f(n)=t(n),f(n+1)=0 形狀表示：以f(i)表示第i位和其后的歌迷總的買票時間的最小值，但不委托第i-1位歌迷票。 總的買票時間的最小值為f(1)。實例五、最少硬幣找錢問題 1問題描畫 設有n種不同面值的硬幣，各硬幣的面值存于數(shù)組T1.n中?，F(xiàn)要用這些面值的硬幣來找錢?？梢赃\用的各種面值的硬幣個數(shù)不限。請計算找出錢數(shù) L 的最少硬幣個數(shù)。 2解題思緒 (

20、1)形狀表示；無妨設0T1T2Tn。當只用面值為T1，T2，Ti的硬幣時，可找出錢數(shù)j的最少硬幣個數(shù)記為Ci,j；當只用這些面值的硬幣找不出錢數(shù)j時，記Ci,j=。問題的解即為Cn,L。 (2)最優(yōu)子構造性質(zhì) 設Sk，k=1,2,i 是只用面值為T1，T2，Ti的硬幣找錢j的一個最優(yōu)找錢序列,即 j = ,而且 ikkTkS1ikjiCkS1,n 那么容易看出：Sk，k=1,2,i-1是只用面值為T1,T2,Ti-1的硬幣找錢j-SiTi的一個最優(yōu)找錢序列。 (2)根據(jù)最優(yōu)子構造性質(zhì),可以建立遞歸關系： Ci,j=, 1min/0kiTkjiCiTjkn初始條件為：Ci,00，il，n;n ,

21、 j mod T10n C1,j= n j div T1, j mod T1=0 n問題的解:找出錢數(shù) L 的最少硬幣個數(shù)為Cn,L。 需求闡明的是，還可以對Ci,j遞歸式作進一步的簡化： 方法二: Ci-1,j；假設j0，即最優(yōu)找錢序列至少有一個Ti，那么在該最優(yōu)找錢序列中去掉一個Ti后的找錢序列應是用用T1.n的硬幣可找出錢數(shù)j-Ti的最優(yōu)找錢序列，其個數(shù)為Cj-Ti。故計算Cj的問題具有最優(yōu)子構造性質(zhì)。 根據(jù)最優(yōu)子構造性質(zhì)，對于任何1jL及1in，假設j-Ti0，那么Cj-Ti所表示的找錢j-Ti的最優(yōu)找錢序列，再加上一枚面值為Ti的硬幣是一種找錢j的方法，且所用的硬幣個數(shù)為Cj-Ti+

22、1。因此，可建立如下的遞歸關系：1min0,1iTjCiTjnin問題的解:找出錢數(shù) L 的最少硬幣個數(shù)為CL。 0, j=0 , 0jT1遞歸關系和初始條件：實例六、編輯間隔問題 1. 問題描畫 設A和B是2個字符串。要用最少的字符操作，將字符串A轉(zhuǎn)換為字符串B。這里所說的字符操作包括： (1)刪除一個字符； (2)插入一個字符； (3)將一個字符改為另一個字符。 將字符串A轉(zhuǎn)換為字符串B所用的最少字符操作 數(shù) 稱 為 字 符 串 A到 B的 編 輯 間 隔 ， 記 為(A,B)。懇求出(A,B)。 2解題思緒 設所給的2個字符串分別為AA1.m和B=B1.n。 形狀表示：思索從字符子串A1

23、.i(按序)變換到字符子串B1.j的最少字符操作問題，有d(i，j) (A1.i， B1.j)。顯然，2個單字符a，b之間的編輯間隔:當ab時，為(a，b)1；當a=b時，為(a，b)0 。問題的解為d(m，n)。 最優(yōu)子構造性質(zhì)：假設Eelek-1ek，k= d(i,j)為從字符串A1.i按序變換到字符串B1.j的一個最少字符操作序列(也稱作d(i,j)的一個最優(yōu)解)，那么最后一個操作ek，屬于以下3種操作之一： (1)將字符Ai改為字符Bj(假設AiBj，那么ek為空操作,不參與計數(shù))，此時E1elek-1為d(i-1，j-1)的一個最優(yōu)解； (2)刪除字符Ai,此時E1elek-1為d(

24、i-1,j)的一個最優(yōu)解； (3)插入字符Bj,此時E1elek-1為d(i,j-1)的一個最優(yōu)解。 因此,問題具有最優(yōu)子構造性質(zhì)。根據(jù)最優(yōu)子構造性質(zhì),建立遞歸關系如下： d(i,j)mind(i-1,j-1)+(Ai,Bj),d(i-1,j)+1,d(i,j-1)+1 初始條件：d(i,0)i,i0m； d(O,j)j，j0n。 問題的解為d(m，n)。實例七、最長公共子序列問題 1.問題描畫 一個給定序列的子序列是在該序列中刪去假設干元素后得到的序列。給定2個序列X和Y，當另一序列Z既是X的子序列又是Y的子序列時，稱Z是序列X和Y的公共子序列。公共子序列中長度最長的公共子序列叫做最長公共子

25、序列。 最長公共子序列(LCS)問題可以表達為：給定2個序列X=x1，xm和Y=y1，yn，要求找出X和Y的一個最長公共子序列。 2解題思緒 解最長公共子序列問題時最容易想到的算法是窮舉搜索法，即對X的每一個子序列，檢查它能否也是Y的子序列，從而確定它能否為X和Y的公共子序列，并且在檢查過程中遴選出最長的公共子序列。X的一切子序列都檢查過后即可求出X和Y的最長公共子序列。 X的一個子序列相應于下標序列1，2，m的個子序列，故X共有2m個不同子序列，窮舉搜索法需求指數(shù)時間。為此，思索能否用動態(tài)規(guī)劃方法求解。 形狀表示：用Ci,j記錄序列X(i)和Y(j)的最長公共子序列的長度，其中X(i)=x1

26、，xi, Y(j)=y1，yj 。原問題最優(yōu)解的長度為Cm,n。 最優(yōu)子構造性質(zhì)： 設序列X=x1，xm和Y=y1，yn的一個最長公共子序列為Z=z1，zk。那么下述結論成立： (1)假設xm = yn，那么zk = xm = yn 且Z(k-1) = z1，zk-1是X(m-1)和Y(n-1)的最長公共子序列。 (2)假設xm yn 且 zk xm，那么Z是X(m-1)和Y的最長公共子序列。 (3)假設xm yn 且 zk yn，那么Z是X和Y(n-1)的最長公共子序列。 證明： (1)用反證法。假設zk xm，那么z1，zk，xm是X和Y的長度為k+l的公共子序列。這與Z是X和Y的一個最長

27、公共子序列矛盾。因此，必有zk = xm = yn。由此可知Z(k-1)=z1，zk-1是X(m-1)和Y(n-1)的一個長度為k-1的公共子序列。假設X(m-1)和Y(n-1)有一個長度大于k-1的公共子序列w，那么將xm加在其尾部將產(chǎn)生X和Y的一個長度大于K的公共子序列。此為矛盾。故 Z(k-1) = z1，zk-1是X(m-1)和Y(n-1)的一個最長公共子序列。 (2)由于zk xm，Z是X(m-1)和Y的一個公共子序列。假設X(m-1)和Y有一個長度大于k的公共子序列w，那么w也是X和Y的一個長度大于k的公共子序列。這與Z是X和y的一個最長公共子序列矛盾。由此可知，Z是X(m-1)和

28、Y的最長公共子序列。 (3)與(2)類似。 上述結論：2個序列的最長公共子序列包含了這2個序列前綴的最長公共子序列。因此，最長公共子序列問題具有最優(yōu)子構造性質(zhì)。 由最長公共子序列問題的最優(yōu)子構造性質(zhì)可知，要找出X=x1，xm和Y=y1，yn的一個最長公共子序列，可按以下方式遞歸地進展： 當 xm = yn時，找出X(m-1)和Y(n-1)的最長公共子序列，然后在其尾部加上xm(=yn)即可得X和Y的一個最長公共子序列。 當xm yn時，必需解2個子問題，即找出X(m-1)和Y的一個最長公共子序列及X和Y(n-1)的一個最長公共子序列。這2個公共子序列中較長者即為X和Y的一個最長公共子序列。 我

29、們來建立子問題的最優(yōu)值Ci,j的遞歸關系。當i=0或j=0時，空序列是X(i)和Y(j)的最長公共子序列，故Ci,j0。其他情況下，由最優(yōu)子構造性質(zhì)，可建立遞歸方程如下: 0 i=0 或j=0;Ci,j Ci-1,j-1+1 i,j0 且xi=yj; maxCi-1,j,Ci,j-1 i,j0 且xiyj; 由此遞歸方程容易看到最長公共子序列問題具有子問題重疊性質(zhì)。 實例八、多邊形游戲問題 1998年國際信息學奧林匹克競賽試題之一 1問題描畫 多邊形游戲是一個單人玩的游戲，開場時有一個由n個頂點構成的多邊形。每個頂點被賦予一個整數(shù)值，每條邊被賦予個運算符“+或“*。一切邊依次用整數(shù)1到n編號。

30、 游戲第1步，將一條邊刪除。 隨后n-1步按以下方法操作。 (1)選擇一條邊E以及由E銜接著的2個頂點Vl和V2； (2)用一個新的頂點取代邊E以及由E銜接著的2個頂點V1和V2。將頂點V1和V2的整數(shù)值經(jīng)過邊上的運算得到的結果賦予新頂點。最后，一切邊都被刪除，游戲終了。游戲的得分就是所剩頂點上的整數(shù)值。 編程義務：對于給定的多邊形，編程計算出最高得分，而且列出一切得到這個最高得分初次被刪除的邊的編號。 數(shù)據(jù)輸入：由文件polygon.in提供輸入數(shù)據(jù)，文件的第1行是所給多邊形的頂點數(shù)n；第2行包含一切邊1n所對應的運算符，以及與順序2邊相關聯(lián)的頂點的數(shù)值(1號邊與2號邊之間是1號頂點的數(shù)值，

31、2號邊與3號邊之間是2號頂點的數(shù)值，依此類推。最后的一個數(shù)值對應于與n號邊和1號邊相關聯(lián)的頂點)。運算符與數(shù)值之間用一個空格分隔。字母t代表運算符“+，字母x代表運算符“*。文件名由鍵盤輸入。 約束條件： 3多邊形的頂點數(shù)50 無論刪除順序如何，一切頂點的數(shù)值均在-32768，32767范圍內(nèi)。 結果輸出：程序運轉(zhuǎn)終了時，將計算結果寫入文件polygon.out中。文件的第1行是計算出的最高得分。第2行是一切得到這個最高得分初次被刪除的邊按升序陳列的編號。 2解題思緒 (1)最優(yōu)子構造性質(zhì)。 設所給的多邊形的頂點和邊的順時針序列為： op1，v1，op2，v2，opn，vn 其中opi表示第i

32、條邊所對應的運算符，vi表示第i個頂點上的數(shù)值，iln。 在所給的多邊形中，從頂點i (1in)開場，長度為j (鏈中有j個頂點)的順時針鏈p (i, j) 可表示為： vi，opi+1，vi+j-1 假設這條鏈的最后一次合并運算在opi+s處發(fā)生(1sj-1)，那么可在opi+s處將鏈分割為2個子鏈p(i, s)和p(i+s, j-s)。 設m1是對子鏈p(i, s)的恣意一種合并方式得到的值，而a和b分別是在一切能夠的合并中得到的最小值和最大值。m2是p(i+s, j-s)的以恣意一種合并方式得到的值，而c和d分別是在一切能夠的合并中得到的最小值和最大值。依此定義有 am1b cm2d 子

33、鏈p(i, s)和p(i+s, j-s)的合并方式取決于p(i, j)在opi+s處斷開后的合并方式，在opi+s處合并后其值為： m(m1)opi+s (m2) 當opi+s“+時，顯然有 a+cmb+d 換句話說，由鏈p(i, j)合并的最優(yōu)性可推出子鏈p(i, s)和p(i+s, j-s)的最優(yōu)性，且最大值對應于子鏈的最大值，最小值對應于子鏈的最小值。 當opi+s“*時，情況有所不同。由于vi可取負整數(shù)，子鏈的最大值相乘未必能得到主鏈的最大值。但是我們留意到最大值一定在邊境點到達，即 minac, ad, bc, bdmmax(ac, ad, bc, bd) 換句話說，主鏈的最大值和最小值可由子鏈的最大值和最小值得到。例如，當mmax=ac時， 最大主鏈由它的2條最小子鏈組成；同理當mmax bd時，最大主鏈由它的2條最大子鏈組成。無論哪種情形發(fā)生，由主鏈的最優(yōu)性均可推出子鏈的最