【正文】 個(gè)例子就非常典型。flag[result[i1]i]==false) { result[i] = result[i1]i。array[1][1] = 1。帶有詳細(xì)注釋的代碼可以在Pku acm 1458 Common Subsequence 動(dòng)態(tài)規(guī)劃題目總結(jié)(五)求兩個(gè)string的最大公共字串，動(dòng)態(tài)規(guī)劃的經(jīng)典問(wèn)題。}for(int i=0。 else result[i][j]= = result[i1][j]result[i][j1]?result[i1][j]:result[i][j1]。通過(guò)這樣的結(jié)論可以和最長(zhǎng)公共子串聯(lián)系起來(lái)(未證明)：S和S39。用二維數(shù)組opt[i][j]記錄字符串a(chǎn)中的前i個(gè)字符與字符串b中的前j個(gè)字符匹配所產(chǎn)生的最大值。i++) opt[0][i] = opt[0][i1]+table(39。opt[num2][num1]即為所求結(jié)果。(i1)==(i+j1)) array[i][j] = true。初始化的時(shí)候和最長(zhǎng)公共子序列不同，因?yàn)榈?行，第0列表示null轉(zhuǎn)化到字符串情況，結(jié)果是字符串的長(zhǎng)度：for(int i=0。創(chuàng)建一個(gè)一維數(shù)組num_array[j]，max_array[],num_array[j]表示序列的元素，max_array[i]表示以第i個(gè)元素結(jié)尾的序列中的最長(zhǎng)下降子序列，初始化為1，對(duì)于一個(gè)max_array[i]，遍歷前面的每個(gè)元素j，如果num_array[j] num_array[i]且max_array[j]= max_array[i],那么max_array[j]就要加1，所以遞推公式為：if(num_array[i]=num_array[j]amp。j++){ if(num_array[i]=num_array[j]amp。ji。為此，我們?cè)黾右粋€(gè)一維數(shù)組B，B[i]表示當(dāng)前序列為i的末尾元素的最小值。 right = Blen。}printf(%d\n,max)。kj。關(guān)鍵部分的c代碼為：for(k=0。帶有詳細(xì)注釋的代碼可以在Pku acm 1050 To the Max 動(dòng)態(tài)規(guī)劃題目總結(jié)(十六)題目的意思很簡(jiǎn)單，在一個(gè)矩陣?yán)锩嬲宜淖泳仃嚕沟米泳仃嚁?shù)值之和到達(dá)最大。 for(int i=1。j=n。i++)，flag[k]表示狀態(tài)是否存在（這里的狀態(tài)是指能否從原石頭堆中分出價(jià)值為k的新石頭堆）。 int i,j,k,sum = 0,max=0。i=6。!flag[j+k*i]) { if(j+k*imax) max = j+k*i。i++) { if(array[i]0) { for(j=max。 if(maxsum/2) max = sum/2。i=m。 }Cost[i][j]1234567891010126101621377411720148111631681093034711266110240137205594502417508960213467470113361802228906100Opt[i][j] 表示前i個(gè)郵局覆蓋前j個(gè)村莊的最小代價(jià)，對(duì)于i=1來(lái)說(shuō)，opt[i][j] = cost[i][j],讓前2個(gè)郵局覆蓋前j個(gè)村莊，也就是i=2的情況，可能是一下情況的最優(yōu)解：第一個(gè)郵局覆蓋第一個(gè)村莊，第二個(gè)郵局覆蓋2j個(gè)村莊，或者第一個(gè)郵局覆蓋第12個(gè)村莊，第二個(gè)村莊覆蓋3j個(gè)村莊，第一個(gè)郵局覆蓋第13個(gè)村莊，第二個(gè)村莊覆蓋4j個(gè)村莊，等等等等。 } } }Opt[i][j]01234567891000101261016213774117201485118161231276862109103345帶有詳細(xì)注釋的代碼可以在Pku acm 1125 Stockbroker Grapevine 動(dòng)態(tài)規(guī)劃題目總結(jié)(十九)有向圖中每一對(duì)頂點(diǎn)間的最短路徑問(wèn)題，典型的弗洛伊德算法。j++) //列 //如果是i==k||j==k||i==j就保持不變，否則取最小值 array[i][j]=(i==k||j==k||i==j)?array[i][j]:((array[i][j](array[i][k]+array[k][j])?array[i][j]:(array[i][k]+array[k][j])))。最后，所有邊都被刪除，游戲結(jié)束。+39。i++) { scanf(%c,amp。i++) { scanf(%c,amp。 for(i=1。 }最后改為了： scanf(%d\n,amp。 } Time Limit Exceeded 發(fā)現(xiàn)代碼中竟然有：this_max = Max(getMaxResult(vertexth,i1,true)*getMaxResult((vertexth+i1)%n+1,lengthi,true), getMaxResult(vertexth,i1,true)*getMaxResult((vertexth+i1)%n+1,lengthi,false),getMaxResult(vertexth,i1,false)*getMaxResult((vertexth+i1)%n+1,lengthi,true),getMaxResult(vertexth,i1,false)*getMaxResult((vertexth+i1)%n+1,lengthi,false))。jlu) 200811。int secondTrue = getMaxResult((vertexth+i1)%n+1,lengthi,true)。 for(i=1。i++) { scanf(%c,amp。 scanf(%d,amp。 scanf(%d,amp。*39。問(wèn)題:對(duì)于給定的多邊形，計(jì)算最高得分。帶有詳細(xì)注釋的代碼可以在Pku acm 1179 Polygon 動(dòng)態(tài)規(guī)劃題目總結(jié)(二十)多邊形游戲是一個(gè)單人玩的游戲，開(kāi)始時(shí)有一個(gè)由n個(gè)頂點(diǎn)構(gòu)成的多邊形。 解決方案：弗洛伊德(floyd)算法321對(duì)于這樣一個(gè)例子： 4 2 2 5 2 6A0[i][j]=cost[i][j]:A0123A1123104510452206220min(6,2+5)322032min(2,2+4)0A2123A3123104min(5,4+6)10min(4,5+2)522062min(2,6+2)063min(2,2+2)203220核心的c代碼如下：for(int k=1。i=n。j=m。0ms。j) { if(flag[j]) { for(k=1。 flag[j+k*i] = true。j=0。i=6。for(int把問(wèn)題轉(zhuǎn)化一下即：由一個(gè)人能否從原大理石堆中取出總價(jià)值為原來(lái)一半的大理石,本題的主要算法是動(dòng)態(tài)規(guī)劃,數(shù)組flag代表狀態(tài),[k]==true時(shí)，說(shuō)明，可以有一人獲得價(jià)值k,另外一人獲得價(jià)值Vk的大理石分配方案。i++) {