【正文】 2]是否為真。 flag[0] = true。 else if(j+k*isum/2amp。修改后的代碼： for(i=1。 flag[j+k*i] = true。讓前i個郵局覆蓋前j個村莊，第i+1個郵局覆蓋第j+1至j+k個村莊(j+k=n)，則狀態(tài)轉(zhuǎn)移方程為opt[i+1][j+k]=min{opt[i][j]+cost[j+1][j+k]。k=j。j+k=m。i++) //行 for(int j=1。隨后n1步按以下方式操作：(1)選擇一條邊E以及由E連接著的2個頂點V1和V2；(2)用一個新的頂點取代邊E以及由E連接著的2個頂點V1和V2。m2是p(i+s，js)的任意一種合并方式得到的值，而c和d分別是在所有可能的合并中得到的最小值和最大值。 for(i=1。 for(i=1。 }就是如果不是最后一個數(shù)字，讀取數(shù)字后讀取一個空格，然而這個時候還是無法正常讀入，因為4后面有一個換行，被錯誤的讀入到edge[1]中，所以在讀取4是加一個\n scanf(%d\n,amp。 if(i!=n) scanf(%c,amp。 scanf(%d,amp。 Time Limit Exceeded 然后想到 可能多次求一個getMaxResult,比如可能多次求一個getMaxResult(3,4,true),所以應(yīng)該將結(jié)果保存起來，這正是動態(tài)規(guī)劃的本質(zhì)！劉汝佳《算法藝術(shù)和信息學(xué)競賽》中115頁講到技藝化搜索，這個例子就非常典型。int secondFalse = getMaxResult((vertexth+i1)%n+1,lengthi,false)。i++) { scanf( %c,amp。 scanf(%d,amp。 if(i!=n) scanf(%c,amp。 }讀入了很多空格，因為空格也是char，然后修改為： scanf(%d,amp。 這道題收獲非常多：，然后調(diào)用一個已經(jīng)定義的函數(shù)max時報錯：term does not evaluate to a function，原因是之前定義了一個int max；所以max(a,b)是把變量錯誤的當(dāng)作函數(shù)使用 ，所以下標要對n取模，這里還有一個技巧，例如當(dāng)n=4時，4對4取模為0，不合要求，所以應(yīng)該減一取模后加一：4t 7 t 4 x 2 x 5開始輸入語句為： scanf(%d,amp。? 如果這條鏈的最后一次合并運算在op[i+s]處發(fā)生(1≤s≤j1)，則可在op[i+s]處將鏈分割為2個子鏈p(i，s)和p(i+s，js)。所有邊依次用整數(shù)從1到n編號。k++) //生成A0,A1,A2...的循環(huán) for(int i=1。j=m。 mid = (i+j)/2。思路：用opt[i][j]記錄把前i個郵局建到前j個村莊中的最優(yōu)解，用cost[i][j]記錄所有在i到j(luò)村莊中，建1個郵局的最小代價。k++) { if(j+k*i==sum/2) return true。}這樣問題就解決了，submit，結(jié)果超時，從joj上試了一下，結(jié)果ac，6s多，距離poj的1s還很遠。k=array[i]。 if(sum%2!=0) return false。j=0。即for } return max。在已知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]。 heigth[i][j]heigth[i+dx[k]][j+dy[k]]) { int num = dp(i+dx[k],j+dy[k])。當(dāng)然252423...321更長。i=r。 } opt[i] = left。以上“2不大于4”，“3在2 6之間”等等的判斷采用二分查找，所以總的時間復(fù)雜度為：O(nlogn)，核心的c代碼如下：for(i=1。 if(max[i]result) result=max[i]。}max_value是最后的結(jié)果。Java關(guān)鍵部分的代碼：for(int i=1。i=n。假如已知AG到GT的最小步數(shù)，AGT到GT的最小步數(shù)，AG到GTT的最小步數(shù)，求AGT到GTT的最小步數(shù)，此時T= =T，這個值是AG到GT的最小步數(shù)，AGT到GT的最小步數(shù)加一(AGT到GT的最小步數(shù)等于AGTT到GTT的最小步數(shù)，加一是將T刪除的一步)，AG到GTT的最小步數(shù)加一(AG到GTT的最小步數(shù)等于AGT到GTTT的最小步數(shù)，加一是在AGT上增加T的一步)。核心的Java代碼：if(array[i][j1]amp。i=num2。39。核心的Java代碼為：totalLCS(string,new StringBuffer(string).reverse().toString())。在求最優(yōu)解時，順著箭頭從后向前尋找公共字串的序號，記錄下來，輸出即可。i=length1。我們定義result[i][j]表示Xi和Yj 的最長子串(LCS).當(dāng)i或j等于0時，result[i][j]=0. LCS問題存在一下遞歸式：result[i][j] = 0 i=0 or j=0result[i][j] = result[i1][j1]+1 Xi= =Yjresult[i][j] = MAX(result[i1][j], result[i][j1]) Xi! =Yj對于以上例子，算法如下：Result[i][j]:abcfba012345600000000a10111111b20122222f30122333c40123333a50123334從最后一個格向上順著箭頭的方向可以找到最長子串的構(gòu)成，在有箭頭組成的線段中，含有斜向上的箭頭對應(yīng)的字符是其中的一個lcs。i++){ array[i][0] = array[i1][1]。 }}帶有詳細注釋的代碼可以在Pku acm 1953 World Cup Noise 動態(tài)規(guī)劃題目總結(jié)(四)給定一個小于45的整數(shù)n，求n位2進制數(shù)中不含相鄰1的數(shù)的個數(shù)。核心的java代碼為：for(i=1。i=0。j++){ //該句是整個動態(tài)規(guī)劃的核心number[i][j]=(number[i+1][j],number[i+1][j+1])+number[i][j]。amp。核心代碼如下：int i,num,count,array[50][2],j=0?？梢岳^續(xù)簡化代碼。i++){ result[i][0] = 0。j++){ if((i1)==(j1)) result[i][j] = result[i1][j1]+1。Pku acm 1159 Palindrome 動態(tài)規(guī)劃題目總結(jié)(七)給一個字符串，求這個字符串最少增加幾個字符能變成回文，如Ab3bd可以增加2個字符變?yōu)榛匚模篈db3bdA。只不過把求最大長度改成了求最大的匹配值。i=num1。,b[i1])。amp。else array[i][j] = ((array[i1][j1]+1, array[i1][j]+1), array[i][j1]+1)。這類問題有兩種算法，一種 T(o) = O(n^2),另一種T(o) = O(nlogn),這里用第一種，在1631 Bridging signals的解題報告中介紹第二種。ji。i++){for(j=1。在O(n^2)的算法中：創(chuàng)建一個一維數(shù)組array[j]，opt[],array[j]表示序列的元素，opt[i]表示以第i個元素結(jié)尾的序列中的最長下降子序列，初始化為1，對于一個opt[i]，遍歷前面的每個元素j，如果array[j]array[i]且opt[j]=opt[i],那么opt[j]就要加1，在這里，遍歷前面的每個元素j，尋找此前最大的子序列時間復(fù)雜度為O(n)，如果我們在一個有序的序列中查找此前最大的序列長度，我們就可以用二分查找，時間復(fù)雜度就會降為O(logn),總的時間復(fù)雜度就會為O(nlogn)。 left = 1。 if(maxopt[i]) max = opt[i]。j+