【文章內(nèi)容簡介】 當(dāng)前為1的序列的末尾元素的最小值)opt111111B4i=2時，2不大于4，所以opt[i]=1,將B[1]更新為2opt111111B2i=3時，6大于2，所以opt[i]=1+1,將B[2]更新為6opt112111B26i=4時，3在2 6之間，所以opt[i]=1+1,將B[2]更新為3opt112211B23i=5時，1小于2，所以opt[i]=1,將B[1]更新為1opt112211B13i=6時，5大于3，所以opt[i]=2+1,將B[3]更新為5opt112213B135opt[6]就是最后的結(jié)果。從構(gòu)建的過程可以容易的證明一下兩點：B是遞增的。B是當(dāng)前序列為i的末尾元素的最小值。以上“2不大于4”，“3在2 6之間”等等的判斷采用二分查找，所以總的時間復(fù)雜度為：O(nlogn)，核心的c代碼如下：for(i=1。i=n。i++){ num = array[i]。 left = 1。 right = Blen。 while(left=right) { mid = (left+right)/2。 if(B[mid]num) left = mid+1。 else right = mid1。 } opt[i] = left。 B[left] = num。 if(Blenleft) Blen = left。 if(maxopt[i]) max = opt[i]。}printf(%d\n,max)。帶有詳細(xì)注釋的代碼可以在Pku acm 1157 LITTLE SHOP OF FLOWERS 動態(tài)規(guī)劃題目總結(jié)(十四)該題也是經(jīng)典的動態(tài)規(guī)劃，題目敘述的依然很麻煩，其實簡化一下就是這樣的：例如下面這個例子就是：3表示行，5表示列，然后在下面的3行5列每一行選一個數(shù)，使這3個數(shù)最大，要求選的數(shù)列數(shù)必須依次增大，就是從左上方向右下方選3個數(shù)使和最大。3 57 23 5 24 165 21 4 10 2321 5 4 20 20 我們用opt定義以當(dāng)前I j為結(jié)尾的花的排序的最大值，用r*(50)表示負(fù)無窮，初始化時第一行為origin[i][j]，后面為r*(50)Opt[][]1234517235241621501501501501503150150150150150從第二行開始，對于第i行第j列，對于i=j,遍歷i1行前j列,求出當(dāng)前最大值。Opt[][]12345172352416215021+74+max(7,23,5)10+max(7,23,5,24)23+max(…)3150150150150150I=3:Opt[][]1234517235241621502819334631501504+max(150,28)20+max()20+max(150,28,19,33)最后取第i行最大值即可，核心的c代碼：for(i=2。i=r。i++) for(j=1。j=c。j++) if(j=i) for(k=1。kj。k++) if(opt[i][j]opt[i1][k]+origin[i][j]) opt[i][j]=opt[i1][k]+origin[i][j]。帶有詳細(xì)注釋的代碼可以在Pku acm 1088 滑雪 動態(tài)規(guī)劃題目總結(jié)(十五)1 2 3 4 516 17 18 19 615 24 25 20 714 23 22 21 813 12 11 10 9一個人可以從某個點滑向上下左右相鄰四個點之一，當(dāng)且僅當(dāng)高度減小。在上面的例子中，一條可滑行的滑坡為2417161。當(dāng)然252423...321更長。事實上，這是最長的一條。輸出最長區(qū)域的長度。Opt[i][j]表示位置i j上最大的下降距離，如果其周圍4個點存在高度比i j高，且opt沒有ij 大的點，則opt[i][j]=opt[周圍]+1；另外，這個問題中存在大量重復(fù)問題，應(yīng)該將計算的結(jié)果存儲起來，避免重復(fù)的計算。關(guān)鍵部分的c代碼為：for(k=0。k4。k++){ if(isIn(i+dx[k],j+dy[k]) amp。amp。 heigth[i][j]heigth[i+dx[k]][j+dy[k]]) { int num = dp(i+dx[k],j+dy[k])。 if(opt[i][j]=num) { opt[i][j] = num+1。 } }}其中const int dx[] = {0,0,1,1},dy[] = {1,1,0,0}。表示一個點周圍的4個點。帶有詳細(xì)注釋的代碼可以在Pku acm 1050 To the Max 動態(tài)規(guī)劃題目總結(jié)(十六)題目的意思很簡單，在一個矩陣?yán)锩嬲宜淖泳仃?，使得子矩陣?shù)值之和到達(dá)最大。其實就是最大子段和問題在二維空間上的推廣。先說一下一維的情況吧：設(shè)有數(shù)組a0,a1…an,找出其中連續(xù)的子段，使它們的和達(dá)到最大。假如對于子段：9 2 16 2 temp[i]表示以ai結(jié)尾的子段中的最大子段和。在已知temp[i]的情況下，求temp [i+1]的方法是：如果temp[i]0 temp [i+1]= temp[i]+ai(繼續(xù)在前一個子段上加上ai),否則temp[i+1]=ai(不加上前面的子段)，也就是說 狀態(tài)轉(zhuǎn)移方程：temp[i] = (temp[i1]0?temp[i1]:0)+buf[i]。對于剛才的例子 temp： 9 11 5 2，然后取temp[]中最大的就是一維序列的最大子段。求一維最大子段和的函數(shù)：int getMax(int buf[100],int n){ int temp[101],max=n*(127)。 memset(temp,0,4*(n+1))。 for(int i=1。i=n。i++) { temp[i] = (temp[i1]0?temp[i1]:0)+buf[i]。 if(maxtemp[i]) max=temp[i]。 } return max。}下面擴展到二維的情況：考察下面題目中的例子：0 2 7 09 2 6 24 1 4 71 8 0 2我們分別用i j表示起始行和終止行，遍歷所有的可能：for(i=1。i=n。i++) for(j=i。j=n。j++) {}我們考察其中一種情況 i=2 j=4，這樣就相當(dāng)與選中了2 3 4三行，求那幾列的組合能獲得最大值，由于總是 2 3 4行，所以我們可以將這3行”捆綁”起來，變?yōu)榍?4(941),11(8+2+1),10(64+0),7(7+22)的最大子段和，ok，問題成功轉(zhuǎn)化為一維的情況！帶有詳細(xì)注釋的代碼可以在Pku acm 1014 Dividing 動態(tài)規(guī)劃題目總結(jié)(十七)剛AC了，趁熱打鐵，寫下解題報告，這道題很早就在joj上做過，當(dāng)時不知道dp，只會用很菜的方法，結(jié)果即使joj這道題僅要求10s還是會超時！思想：本題是找按價值均分大理石的方案是否存在，由于分配時不能破壞大理石，所以有個顯而易見的剪枝：當(dāng)所有的大理石的總價值為奇數(shù)時肯定不能被均分。把問題轉(zhuǎn)化一下即：由一個人能否從原大理石堆中取出總價值為原來一半的大理石,本題的主要算法是動態(tài)規(guī)劃,數(shù)組flag代表狀態(tài),[k]==true時，說明，可以有一人獲得價值k,另外一人獲得價值Vk的大理石分配方案。反之若flag[k]=[sum/2]是true還是false，顯然有flag[0]==true的方案存在，即一個人什么都不分，另外一個人拿走全部的大理石.設(shè)i（16）為石頭的價值，試想若flag[k]==true，如果能再向k中增加一價值為i的大理石，則flag[k+i]==，一個是價值另一個是數(shù)量，這里array[i]代表價值為i的大理石的數(shù)量，我們根據(jù)其中一個屬性：價值來劃分階段。即for(int160