acm動(dòng)態(tài)規(guī)劃總結(jié)-資料下載頁(yè)
2025-08-04 22:57本頁(yè)面
【正文】 00000) { for(k=1。j+k=m。k++) { if(opt[i+1][j+k]opt[i][j]+cost[j+1][j+k]) { opt[i+1][j+k] = opt[i][j]+cost[j+1][j+k]。 } } }Opt[i][j]01234567891000101261016213774117201485118161231276862109103345帶有詳細(xì)注釋的代碼可以在Pku acm 1125 Stockbroker Grapevine 動(dòng)態(tài)規(guī)劃題目總結(jié)(十九)有向圖中每一對(duì)頂點(diǎn)間的最短路徑問(wèn)題，典型的弗洛伊德算法。問(wèn)題描述：已知一個(gè)含有n個(gè)頂點(diǎn)的各邊權(quán)值均大于0的帶權(quán)有向圖，對(duì)每對(duì)頂點(diǎn)vi！=vj，要求求出每一對(duì)頂點(diǎn)之間的最短路徑和最短路徑長(zhǎng)度。 解決方案：弗洛伊德(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。k=n。k++) //生成A0,A1,A2...的循環(huán) for(int i=1。i=n。i++) //行 for(int j=1。j=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])))。最后根據(jù)題意，取每行最大值中的最小值即可。帶有詳細(xì)注釋的代碼可以在Pku acm 1179 Polygon 動(dòng)態(tài)規(guī)劃題目總結(jié)(二十)多邊形游戲是一個(gè)單人玩的游戲，開(kāi)始時(shí)有一個(gè)由n個(gè)頂點(diǎn)構(gòu)成的多邊形。每個(gè)頂點(diǎn)被賦予一個(gè)整數(shù)值，每條邊被賦予一個(gè)運(yùn)算符“+”或“*”。所有邊依次用整數(shù)從1到n編號(hào)。游戲第1步，將一條邊刪除。隨后n1步按以下方式操作：(1)選擇一條邊E以及由E連接著的2個(gè)頂點(diǎn)V1和V2；(2)用一個(gè)新的頂點(diǎn)取代邊E以及由E連接著的2個(gè)頂點(diǎn)V1和V2。將由頂點(diǎn)V1和V2的整數(shù)值通過(guò)邊E上的運(yùn)算得到的結(jié)果賦予新頂點(diǎn)。最后，所有邊都被刪除，游戲結(jié)束。游戲的得分就是所剩頂點(diǎn)上的整數(shù)值。問(wèn)題:對(duì)于給定的多邊形，計(jì)算最高得分。分析：? 在所給多邊形中，從頂點(diǎn)i(1≤i≤n)開(kāi)始，長(zhǎng)度為j(鏈中有j個(gè)頂點(diǎn))的順時(shí)針鏈p(i，j) 可表示為v[i]，op[i+1]，…，v[i+j1]。? 如果這條鏈的最后一次合并運(yùn)算在op[i+s]處發(fā)生(1≤s≤j1)，則可在op[i+s]處將鏈分割為2個(gè)子鏈p(i，s)和p(i+s，js)。? 設(shè)m1是對(duì)子鏈p(i，s)的任意一種合并方式得到的值，而a和b分別是在所有可能的合并中得到的最小值和最大值。m2是p(i+s，js)的任意一種合并方式得到的值，而c和d分別是在所有可能的合并中得到的最小值和最大值。依此定義有a≤m1≤b，c≤m2≤d(1)當(dāng)op[i+s]=39。+39。時(shí)，顯然有a+c≤m≤b+d(2)當(dāng)op[i+s]=39。*39。時(shí)，有min{ac，ad，bc，bd}≤m≤max{ac，ad，bc，bd} ? 換句話(huà)說(shuō)，主鏈的最大值和最小值可由子鏈的最大值和最小值得到。 這道題收獲非常多：，然后調(diào)用一個(gè)已經(jīng)定義的函數(shù)max時(shí)報(bào)錯(cuò)：term does not evaluate to a function，原因是之前定義了一個(gè)int max；所以max(a,b)是把變量錯(cuò)誤的當(dāng)作函數(shù)使用 ，所以下標(biāo)要對(duì)n取模，這里還有一個(gè)技巧，例如當(dāng)n=4時(shí)，4對(duì)4取模為0，不合要求，所以應(yīng)該減一取模后加一：4t 7 t 4 x 2 x 5開(kāi)始輸入語(yǔ)句為： scanf(%d,amp。n)。 for(i=1。i=n。i++) { scanf(%c,amp。edge[i])。 scanf(%d,amp。vertex[i])。 }讀入了很多空格，因?yàn)榭崭褚彩莄har，然后修改為： scanf(%d,amp。n)。 for(i=1。i=n。i++) { scanf(%c,amp。edge[i])。 scanf(%d,amp。vertex[i])。 if(i!=n) scanf(%c,amp。edge[0])。 }就是如果不是最后一個(gè)數(shù)字，讀取數(shù)字后讀取一個(gè)空格，然而這個(gè)時(shí)候還是無(wú)法正常讀入，因?yàn)?后面有一個(gè)換行，被錯(cuò)誤的讀入到edge[1]中，所以在讀取4是加一個(gè)\n scanf(%d\n,amp。n)。 for(i=1。i=n。i++) { scanf(%c,amp。edge[i])。 scanf(%d,amp。vertex[i])。 if(i!=n) scanf(%c,amp。edge[0])。 }最后改為了： scanf(%d\n,amp。n)。 for(i=1。i=n。i++) { scanf( %c,amp。edge[i])。 scanf(%d,amp。vertex[i])。 } 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))。這種語(yǔ)句，不Time Limit Exceeded 就奇怪了，接著改為：用變量保存結(jié)果，然后取最大值：int firstTrue = getMaxResult(vertexth,i1,true)。int secondTrue = getMaxResult((vertexth+i1)%n+1,lengthi,true)。int firstFalse = getMaxResult(vertexth,i1,false)。int secondFalse = getMaxResult((vertexth+i1)%n+1,lengthi,false)。this_max = Max(firstTrue*secondTrue,firstTrue*secondFalse,firstFalse*secondTrue,firstFalse*secondFalse)。 Time Limit Exceeded 然后想到 可能多次求一個(gè)getMaxResult,比如可能多次求一個(gè)getMaxResult(3,4,true),所以應(yīng)該將結(jié)果保存起來(lái)，這正是動(dòng)態(tài)規(guī)劃的本質(zhì)！劉汝佳《算法藝術(shù)和信息學(xué)競(jìng)賽》中115頁(yè)講到技藝化搜索，這個(gè)例子就非常典型。定義一個(gè)3維數(shù)組，然后初始化為一個(gè)很小的值，然后調(diào)用getMaxResult時(shí)先判斷是不是已經(jīng)計(jì)算過(guò)了(就是數(shù)組中是不是已經(jīng)有值了)，如果計(jì)算過(guò)就直接返回，否則在返回之前將值保存到數(shù)組中！結(jié)果AC 帥，15ms帶有詳細(xì)注釋的代碼可以在 by 蘇強(qiáng)(neuqamp。jlu) 20081
數(shù)學(xué)相關(guān)推薦
鄂ICP備17016276號(hào)-1