【正文】 的），階段變量可以確定狀態(tài)所在階段，而狀態(tài)變量則反映狀態(tài)本身的性質(zhì)。而前面提到的二維狀態(tài)劃分只有Skiing一題（F[I,J]表示滑到第I行第J列的點(diǎn)時(shí)存在的最長(zhǎng)滑坡長(zhǎng)度），因?yàn)檫@里I和J兩個(gè)變量才能確定狀態(tài)所在的階段。下面了列舉幾個(gè)典型的線性動(dòng)態(tài)規(guī)劃題圖：UVA 10684 The Jackpot【題目描述】 某人想迅速變得富有，但是他還不想工作?！据斎敫袷健枯斎氲谝恍邪粋€(gè)正整數(shù)N（N≤10000），接下里包含N個(gè)整數(shù)，它們的絕對(duì)值都不超過1000?！緲永斎搿?12 4 10 4 9【樣例輸出】13 我們稱該類問題為最大連續(xù)數(shù)字和。這樣就構(gòu)造出一個(gè)線性動(dòng)態(tài)規(guī)劃算法了，以下是它的一個(gè)經(jīng)典應(yīng)用：NECPC2007 Sum Of SubRectangular Parallelepiped【題目描述】現(xiàn)有一個(gè)棱長(zhǎng)為n的立方體，可以分成n3個(gè)1*1*1的單位立方體?，F(xiàn)在要求在這個(gè)立方體找到一個(gè)包含完整單位立方體的長(zhǎng)方體，使得該長(zhǎng)方體內(nèi)所有單位立方體的數(shù)和最大。接下來n個(gè)n2的數(shù)字矩陣，每個(gè)數(shù)字矩陣代表一層，每個(gè)數(shù)字代表一個(gè)單位立方體的整數(shù)值?！緲永斎搿?1 22 11 –22 1【樣例輸出】6 最基礎(chǔ)的方法是“直譯”枚舉過程，時(shí)間復(fù)雜度O（n9）。如圖所示，在統(tǒng)計(jì)長(zhǎng)方體2時(shí)，只要將長(zhǎng)方體1的統(tǒng)計(jì)結(jié)果加上長(zhǎng)方體3就可以了，而不必按上述算法那樣重新進(jìn)行計(jì)算。 而對(duì)于每個(gè)平面的矩形有一種經(jīng)典的壓縮方法，設(shè)rec[x,y,z]表示z軸坐標(biāo)為z的水平面中矩形（1,1,x,y）的數(shù)和。 有了上面的關(guān)系式，我們下面要做的只是枚舉z,x1,x2,y1,y2來查找最優(yōu)解。總的時(shí)間復(fù)雜度為O（n5）。 合唱隊(duì)形是指這樣的一種隊(duì)形：設(shè)K位同學(xué)從左到右依次編號(hào)為1，2…，K，他們的身高分別為T1，T2，…，TK，則他們的身高滿足T1...TiTi+1…TK（1≤i≤K）?！据斎敫袷健康谝恍惺且粋€(gè)整數(shù)N(2≤N≤106)，表示同學(xué)的總數(shù)?！据敵龈袷健恐话粋€(gè)整數(shù)，就是最少需要幾位同學(xué)出列。I和J都需要枚舉，所以時(shí)間復(fù)雜度為O（n2）。對(duì)于每一個(gè)A[J]，只要在G序列中找到一個(gè)最大的I，使得G[I] A[J]，那么就可以在它的后面插入A[J]就形成了當(dāng)前的最長(zhǎng)上升子序列，接下來需要更新G（當(dāng)然只是其中的一個(gè)元素）。 另外值得一提的就是在解決合唱隊(duì)型這個(gè)問題時(shí)，不要枚舉分割點(diǎn)之后再分別向兩個(gè)方向動(dòng)態(tài)規(guī)劃，那樣的時(shí)間復(fù)雜度為O（n2logn）。 其他線性動(dòng)態(tài)規(guī)劃舉例 很多其他的線性動(dòng)態(tài)規(guī)劃基本都是大同小異，它們的共同點(diǎn)就是沿著一個(gè)軸（如坐標(biāo)軸、時(shí)間軸）進(jìn)行規(guī)劃；由于沒有狀態(tài)變量，它們的狀態(tài)就是用F[I]表示到軸上第I個(gè)點(diǎn)為止的題目所要求的最優(yōu)解。USACO Score Inflation【題目描述】學(xué)生在我們USACO的競(jìng)賽中的得分越多我們?cè)礁吲d。我們可以從幾個(gè)種類中選取競(jìng)賽的題目，這里的一個(gè)“種類”是指一個(gè)競(jìng)賽題目的集合，解決集合中的題目需要相同多的時(shí)間并且能得到相同的分?jǐn)?shù)?！据斎敫袷健枯斎氚ǜ?jìng)賽的時(shí)間，M(1≤M≤10,000)和N，“種類”的數(shù)目（1≤N≤10,000）?！据敵龈袷健恐话粋€(gè)整數(shù)，就是在競(jìng)賽的時(shí)間中得到最大的分?jǐn)?shù)。則F[I] = Max {F[IA[J]] + B[J]}，其中A[J]為第J類題目的時(shí)間，B[J]為第J類題目可得分?jǐn)?shù)。 事實(shí)上，很多種類的題目是廢題（用時(shí)多，得分少）。如果我們只取性價(jià)比最好的前K種題目，那么動(dòng)態(tài)規(guī)劃的時(shí)間復(fù)雜度就為O(MK)。Noip2005 過河【題目描述】在河上有一座獨(dú)木橋，一只青蛙想沿著獨(dú)木橋從河的一側(cè)跳到另一側(cè)。由于橋的長(zhǎng)度和青蛙一次跳過的距離都是正整數(shù)，我們可以把獨(dú)木橋上青蛙可能到達(dá)的點(diǎn)看成數(shù)軸上的一串整點(diǎn)：0，1，……，L（其中L是橋的長(zhǎng)度）。青蛙從橋的起點(diǎn)開始，不停的向終點(diǎn)方向跳躍。當(dāng)青蛙跳到或跳過坐標(biāo)為L(zhǎng)的點(diǎn)時(shí)，就算青蛙已經(jīng)跳出了獨(dú)木橋。你的任務(wù)是確定青蛙要想過河，最少需要踩到的石子數(shù)。第二行有三個(gè)正整數(shù)S，T，M，分別表示青蛙一次跳躍的最小距離，最大距離，及橋上石子的個(gè)數(shù)，其中1≤S≤T≤10，1≤M≤100。所有相鄰的整數(shù)之間用一個(gè)空格隔開。【樣例輸入】102 3 52 3 5 6 7【樣例輸出】2看到題目首先想到的是時(shí)間復(fù)雜度為O(TL)的線性動(dòng)態(tài)規(guī)劃。但是L的上限為109，這種算法顯然是不行的。因此，將障礙點(diǎn)按升序排列，當(dāng)兩相鄰障礙點(diǎn)之間距離較大時(shí)，可適當(dāng)縮小兩障礙點(diǎn)之間距離，但不影響最終結(jié)果。對(duì)于任意的S和T（S≠T時(shí)），那么每次至少有T和T1兩種跳法。這樣一來，我們就可以把間距超過T(T1) + K的兩點(diǎn)間距離化為T(T1) + K。 一維狀態(tài)劃分的非線性動(dòng)態(tài)規(guī)劃下面要討論的是一維狀態(tài)劃分的非線性動(dòng)態(tài)規(guī)劃問題。物品I的重量是WI，其價(jià)值為VI，背包的容量為C。每考慮一件物品為一個(gè)階段，對(duì)于每一物品來說，都只有取和不取兩種可能。實(shí)際上，01背包問題和Number Triangles問題只是在做決策時(shí)略有不同，前者考慮取或者不取，而后者考慮要走到左邊還是右邊。由于動(dòng)態(tài)規(guī)劃的無后效性，我們只需記錄相鄰的兩個(gè)階段的狀態(tài)即可，這就是滾動(dòng)數(shù)組的原理。更讓他高興的是，媽媽昨天對(duì)他說：“你的房間需要購(gòu)買哪些物品，怎么布置，你說了算，只要不超過N元錢就行”。每個(gè)主件可以有0個(gè)、1個(gè)或2個(gè)附件。金明想買的東西很多，肯定會(huì)超過媽媽限定的N元。他還從因特網(wǎng)上查到了每件物品的價(jià)格（都是10元的整數(shù)倍）。 設(shè)第j件物品的價(jià)格為v[j]，重要度為w[j]，共選中了k件物品，編號(hào)依次為j1，j2，……，jk，則所求的總和為： v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk]。 【輸入格式】 第1行為兩個(gè)正整數(shù)，用一個(gè)空格隔開： N 和m，（其中N（32000）表示總錢數(shù)，m（60）為希望購(gòu)買物品的個(gè)數(shù)。（其中v表示該物品的價(jià)格（v10000），p表示該物品的重要度（1~5），q表示該物品是主件還是附件。 【樣例輸入】 1000 5800 2 0400 5 1300 5 1400 3 0500 2 0【樣例輸出】 2200 題目已經(jīng)提示我們每個(gè)主件可以有0個(gè)，1個(gè)或2個(gè)附件。設(shè)F[I,J]表示前I種組合花費(fèi)為J獲得的最大重要度乘積和，則有：F[I,J] = Max ( F[I1,J],F[I1,JV[I,0]]+V[I,0]*W[I,0],F[I1,JV[I,0]V[I,1]]+V[I,0]*W[I,0]+V[I,1]*W[I,1],F[I1,JV[I,0]V[I,2]]+V[I,0]*W[I,0]+V[I,2]*W[I,2],F[I1,JV[I,0]V[I,1]V[I,2]]+V[I,0]*W[I,0]+V[I,1]*W[I,1]+V[I,2]*W[I,2])還可以利用“每件物品都是10元的整數(shù)倍”的條件，總的時(shí)間復(fù)雜度為O（NM）?，F(xiàn)在有P（P≤500)個(gè)房子。住房有以下要求：，不能再住其他人。對(duì)女人也是一樣。【輸入格式】 第1行為四個(gè)正整數(shù)，N,M,C和P?！据敵龈袷健?只有一個(gè)正整數(shù)，為這N+M個(gè)人住房的最少費(fèi)用（longint范圍內(nèi)）。這樣我們可以枚舉夫婦數(shù)（0或者1），這樣就去掉了夫婦的這個(gè)限制。則顯然有F[I,J,K]=Min {F[I1,J,K], F[I1,J+B[I],K]+C[I], F[I1,J,K+B[I]]+C[I]}，時(shí)間復(fù)雜度為O(P M N)。當(dāng)人數(shù)超過R的時(shí)候，性價(jià)比比較高的房間就必然會(huì)被使用，那么先把所有房間按照性價(jià)比排序然后按順序分放直到人數(shù)少于R為止，時(shí)間復(fù)雜度就降為O(P R2)。話說齊王和田忌又要賽馬了，他們各派出N匹馬（N≤2000），每場(chǎng)比賽，輸?shù)囊环綄⒁o贏的一方200兩黃金，如果是平局的話，雙方都不必拿出錢。請(qǐng)問田忌該如何安排自己的馬去對(duì)抗齊王的馬，才能贏最多的錢？【輸入格式】 第1行為一個(gè)正整數(shù)N?！据敵龈袷健?只有一個(gè)正整數(shù)，即田忌能贏得的最大錢數(shù)。把田忌的馬放左邊，把齊王的馬放右邊。因?yàn)樘锛烧莆沼斜荣惖闹鲃?dòng)權(quán)，他總是根據(jù)齊王所出的馬來分配自己的馬，所以這里不妨設(shè)齊王的出馬順序是按馬的速度從高到低出的。 ，那么應(yīng)該用最差的一匹馬去輸給齊王最強(qiáng)的馬；216。 如果全部打平的話，如果齊王馬的速度分別是1 2 3，田忌馬的速度也是1 2 3，每次選擇打平的話，田忌一分錢也得不到，而如果選擇先用速度為1的馬輸給速度為3的馬的話，可以贏得200兩黃金。而如果先用速度為3的馬去打平的話，可以贏得200兩黃金。那先把田忌和齊王的馬分別按從強(qiáng)到弱排序，設(shè)F[I,J]表示齊王按從強(qiáng)到弱的順序出馬和田忌進(jìn)行了I場(chǎng)比賽之后，田忌從頭取了J匹較強(qiáng)的馬出戰(zhàn)所能夠得到的最大錢數(shù)。 壓縮狀態(tài)的動(dòng)態(tài)規(guī)劃下面介紹一下壓縮狀態(tài)的動(dòng)態(tài)規(guī)劃。當(dāng)集合中元素個(gè)數(shù)的不定性或范圍大時(shí)，如果直接開數(shù)組存，索引數(shù)組的編程復(fù)雜度太高（而且程序時(shí)間效率低下），所以要進(jìn)行集合編碼。下面舉一個(gè)經(jīng)典的問題作為例子：Noi2001 炮兵陣地【題目描述】司令部的將軍們打算在N*M的網(wǎng)格地圖上部署他們的炮兵部隊(duì)。在每一格平原地形上最多可以布置一支炮兵部隊(duì)（山地上不能夠部署炮兵部隊(duì)）；一支炮兵部隊(duì)在地圖上的攻擊范圍如圖中黑色區(qū)域所示： 如果在地圖中的灰色所標(biāo)識(shí)的平原上部署一支炮兵部隊(duì)，則圖中的黑色的網(wǎng)格表示它能夠攻擊到的區(qū)域：沿橫向左右各兩格，沿縱向上下各兩格。從圖上可見炮兵的攻擊范圍不受地形的影響?！据斎敫袷健?第一行包含兩個(gè)由空格分割開的正整數(shù)，分別表示N和M；接下來的N行，每一行含有連續(xù)的M個(gè)字符(39?；蛘?9。)，中間沒有空格。N≤100；M≤10?！緲永斎搿?5 4PHPPPPHHPPPPPHPPPHHP【樣例輸出】 6 這是一道比較麻煩的問題，如果某點(diǎn)是P，就可以有放兵與不放兵兩種方案，但對(duì)于在I和J位置之前的所有P的擺放方案有多種方案，我們將這兩種方案分別去嘗試與P(I,J)之前所有方案結(jié)合，則P(I,J)又會(huì)有很多種方案。即使是一個(gè)全為P的空列上一共也只有60種合法的炮兵放置方法。則有F[I,X,Y] = Max{F[I1,Z,X] + N[Y]}，其中要求沒有互相攻擊的可能，N[Y]表示方案Y對(duì)應(yīng)的炮兵數(shù)。下面我們用位運(yùn)算建立它們之間的聯(lián)系，需要使用異或運(yùn)算符（^），[0000010111]2^[0000010000]2=[0000000111]2，即23^(1(51)) = 7，這大大方便了我們?cè)跔顟B(tài)壓縮動(dòng)態(tài)規(guī)劃中進(jìn)行狀態(tài)轉(zhuǎn)移。s house. The lucky fish is the one who has the highest score(what a bad thing!). There are several posthouses on the way to bailey39。t get there in time, you will lose it.Luckily, with another friend angela39。t calculate the travel path that makes him the lucky fish. Fortunately, you are kind enough to help him, and what you need only to do is the calculation.【輸入格式】 Each test case starts with a single integer n (2 = n = 11) denoting the number of posthouses. The posthouses are numbered from 1 to n. Then a matrix with n+2 rows and n+2 columns followes. The integer in row i(row j) and column j(column i) is the time fish will cost to travel between place i and place j directly. A zero means that there is not a direct way connecting place i and j. fish starts with place 0 and bailey39。s house in time, please output Fish can fly! and the highest score he can get separated by just one space. If he can39。設(shè)F[I,S]表示在第I個(gè)點(diǎn)，經(jīng)過路徑為S的最少時(shí)間，則有：F[I,S] = Min {F[J,S^(1I)] + D[I,J]}其中J=1..N且(1J)amp。最后在規(guī)定時(shí)間內(nèi)的路徑中選擇一條分?jǐn)?shù)最高的，時(shí)間復(fù)雜度為O（N2N）。首先介紹一個(gè)經(jīng)典問題：最長(zhǎng)公共子序列（LCS）。例如，字符串a(chǎn)bcabcabb與bcacacbb的最長(zhǎng)公共子序列為bcacabb。 我們每考慮一個(gè)相同的字母為一個(gè)階段，對(duì)于每一個(gè)相同的字母來說，都可以在它以前最大長(zhǎng)度的基礎(chǔ)上加1。LEN_B），構(gòu)造LCS的時(shí)間復(fù)雜度：O（LEN_A + LEN_B）。任意給定的一個(gè)字符串，通過插入若干字符，都可以變成一個(gè)回文詞?！据斎敫袷健?第一行包含一個(gè)數(shù)字N（N≤5000），表示字符串的長(zhǎng)度，第二行包含一個(gè)長(zhǎng)度為N的字符串?！緲永斎搿?5Ab3bd【樣例輸出】 2 這個(gè)問題相