【文章內(nèi)容簡(jiǎn)介】 取得最大值100，這時(shí)整個(gè)算法的時(shí)間復(fù)雜度為O(100MT)，可以在1s內(nèi)通過全部測(cè)試數(shù)據(jù)。 一維狀態(tài)劃分的非線性動(dòng)態(tài)規(guī)劃下面要討論的是一維狀態(tài)劃分的非線性動(dòng)態(tài)規(guī)劃問題。其中最為經(jīng)典的模型就是01背包問題：給定N種物品和一背包。物品I的重量是WI，其價(jià)值為VI，背包的容量為C。選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大，求這個(gè)最大價(jià)值。每考慮一件物品為一個(gè)階段，對(duì)于每一物品來說，都只有取和不取兩種可能。那么設(shè)F[I,J]表示考慮前I個(gè)物品取的總重量不超過J的最大價(jià)值，則有狀態(tài)轉(zhuǎn)移方程：F[I,J] = Max （F[I1,J], F[I1,JWI] + VI）。實(shí)際上，01背包問題和Number Triangles問題只是在做決策時(shí)略有不同，前者考慮取或者不取，而后者考慮要走到左邊還是右邊。最后提醒一下，01背包是一個(gè)NP問題，時(shí)空復(fù)雜度均為O（NW），當(dāng)W的規(guī)模比較大時(shí)（不是很過分的大），空間開銷隨之增大，我們可以利用滾動(dòng)數(shù)組解決這一問題。由于動(dòng)態(tài)規(guī)劃的無后效性，我們只需記錄相鄰的兩個(gè)階段的狀態(tài)即可，這就是滾動(dòng)數(shù)組的原理。Noip2006 金明的預(yù)算方案【題目描述】金明今天很開心，家里購(gòu)置的新房就要領(lǐng)鑰匙了，新房里有一間金明自己專用的很寬敞的房間。更讓他高興的是，媽媽昨天對(duì)他說：“你的房間需要購(gòu)買哪些物品，怎么布置，你說了算，只要不超過N元錢就行”。今天一早，金明就開始做預(yù)算了，他把想買的物品分為兩類：主件與附件，附件是從屬于某個(gè)主件的，下表就是一些主件與附件的例子： 主件 附件 電腦 打印機(jī)，掃描儀 書柜 圖書 書桌 臺(tái)燈，文具 工作椅 無 如果要買歸類為附件的物品，必須先買該附件所屬的主件。每個(gè)主件可以有0個(gè)、1個(gè)或2個(gè)附件。附件不再有從屬于自己的附件。金明想買的東西很多，肯定會(huì)超過媽媽限定的N元。于是，他把每件物品規(guī)定了一個(gè)重要度，分為5等：用整數(shù)1~5表示，第5等最重要。他還從因特網(wǎng)上查到了每件物品的價(jià)格（都是10元的整數(shù)倍）。他希望在不超過N元（可以等于N元）的前提下，使每件物品的價(jià)格與重要度的乘積的總和最大。 設(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]。（其中*為乘號(hào)） 請(qǐng)你幫助金明設(shè)計(jì)一個(gè)滿足要求的購(gòu)物單。 【輸入格式】 第1行為兩個(gè)正整數(shù)，用一個(gè)空格隔開： N 和m，（其中N（32000）表示總錢數(shù)，m（60）為希望購(gòu)買物品的個(gè)數(shù)。）從第2行到第m+1行，第j行給出了編號(hào)為j1的物品的基本數(shù)據(jù)，每行有3個(gè)非負(fù)整數(shù)v ,p 和q 。（其中v表示該物品的價(jià)格（v10000），p表示該物品的重要度（1~5），q表示該物品是主件還是附件。如果q=0，表示該物品為主件，如果q0，表示該物品為附件，q是所屬主件的編號(hào)）【輸出格式】 只有一個(gè)正整數(shù)，為不超過總錢數(shù)的物品的價(jià)格與重要度乘積的總和的最大值（200000）。 【樣例輸入】 1000 5800 2 0400 5 1300 5 1400 3 0500 2 0【樣例輸出】 2200 題目已經(jīng)提示我們每個(gè)主件可以有0個(gè)，1個(gè)或2個(gè)附件。那么考慮每套主件與附件的組合，最多有5種處理方法：不取，主件，主件+附件A，主件+附件B和主件+附件A+附件B。設(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）。NoiWC2007 Hotel【題目描述】有N個(gè)男人，M個(gè)女人，其中有C（1≤C≤M,N≤500）對(duì)夫婦要住房?，F(xiàn)在有P（P≤500)個(gè)房子。每個(gè)房子有個(gè)費(fèi)用Ci和床位Bi（Bi≤5）。住房有以下要求：，不能再住其他人。：一個(gè)房間住了男人后，不能再住女人。對(duì)女人也是一樣。求這N+M個(gè)人住房的最少費(fèi)用?！据斎敫袷健?第1行為四個(gè)正整數(shù)，N,M,C和P。以下P行每行包含兩個(gè)正整數(shù)Ci和Bi?！据敵龈袷健?只有一個(gè)正整數(shù)，為這N+M個(gè)人住房的最少費(fèi)用（longint范圍內(nèi)）?！緲永斎搿?3 2 2 430 420 110 220 2【樣例輸出】 40 事實(shí)上我們可以發(fā)現(xiàn)按照第2條住房的夫婦數(shù)不會(huì)超過1，如果有2對(duì)夫婦那么可以交換一下，在同樣代價(jià)下反而能住更多人。這樣我們可以枚舉夫婦數(shù)（0或者1），這樣就去掉了夫婦的這個(gè)限制。設(shè)F[I,J,K]表示前I個(gè)房間安排好后，還剩下J男K女的最小費(fèi)用。則顯然有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)。和前面說過的Score Inflation一樣，在人數(shù)比較多的時(shí)候可以加入貪心思想。當(dāng)人數(shù)超過R的時(shí)候，性價(jià)比比較高的房間就必然會(huì)被使用，那么先把所有房間按照性價(jià)比排序然后按順序分放直到人數(shù)少于R為止，時(shí)間復(fù)雜度就降為O(P R2)。Shanghai2004 The Horse Racing【題目描述】中國(guó)古代的歷史故事“田忌賽馬”是為大家所熟知的。話說齊王和田忌又要賽馬了，他們各派出N匹馬（N≤2000），每場(chǎng)比賽，輸?shù)囊环綄⒁o贏的一方200兩黃金，如果是平局的話，雙方都不必拿出錢?，F(xiàn)在每匹馬的速度值是固定而且已知的，而齊王出馬也不管田忌的出馬順序。請(qǐng)問田忌該如何安排自己的馬去對(duì)抗齊王的馬，才能贏最多的錢？【輸入格式】 第1行為一個(gè)正整數(shù)N。第2行和第3行每行包含N個(gè)正整數(shù)，分別表示田忌和齊王帳下馬的速度?！据敵龈袷健?只有一個(gè)正整數(shù)，即田忌能贏得的最大錢數(shù)?！緲永斎搿?392 83 7195 87 74【樣例輸出】 200這個(gè)問題很顯然可以轉(zhuǎn)化成一個(gè)二分圖最佳匹配的問題。把田忌的馬放左邊，把齊王的馬放右邊。田忌的馬A和齊王的B之間，如果田忌的馬勝，則連一條權(quán)為200的邊；如果平局，則連一條權(quán)為0的邊；如果輸，則連一條權(quán)為－200的邊，但二分圖最佳匹配算法的復(fù)雜度為O（N3）。因?yàn)樘锛烧莆沼斜荣惖闹鲃?dòng)權(quán)，他總是根據(jù)齊王所出的馬來分配自己的馬，所以這里不妨設(shè)齊王的出馬順序是按馬的速度從高到低出的。對(duì)于這樣的假設(shè)，我們歸納出如下貪心策略：216。 ，那么應(yīng)該用最差的一匹馬去輸給齊王最強(qiáng)的馬；216。 ，那就用這匹馬去贏齊王剩下的最強(qiáng)的馬； 這兩點(diǎn)是顯然的，關(guān)鍵在于田忌最快的馬和齊王最快的馬打平，那么田忌是選擇平還是輸呢？ 252。 如果全部打平的話，如果齊王馬的速度分別是1 2 3，田忌馬的速度也是1 2 3，每次選擇打平的話，田忌一分錢也得不到，而如果選擇先用速度為1的馬輸給速度為3的馬的話，可以贏得200兩黃金。而如果全部輸?shù)舻脑?，如果齊王馬的速度分別是1 3，田忌馬的速度分別是2 3，田忌一勝一負(fù)，仍然一分錢也拿不到。而如果先用速度為3的馬去打平的話，可以贏得200兩黃金。這里雖然出現(xiàn)了分支，但我們得知田忌一定是將他馬按速度排序之后，從兩頭取馬去和齊王的馬比賽。那先把田忌和齊王的馬分別按從強(qiáng)到弱排序，設(shè)F[I,J]表示齊王按從強(qiáng)到弱的順序出馬和田忌進(jìn)行了I場(chǎng)比賽之后，田忌從頭取了J匹較強(qiáng)的馬出戰(zhàn)所能夠得到的最大錢數(shù)。則有：F[I,J] = Max {F[I1,J] + G[N(IJ)+1,I],F[I1,J1]+G[J,I]}，其中G[J,I]表示田忌的第J匹馬和齊王的第I匹馬比賽的獲利。 壓縮狀態(tài)的動(dòng)態(tài)規(guī)劃下面介紹一下壓縮狀態(tài)的動(dòng)態(tài)規(guī)劃。這種動(dòng)態(tài)規(guī)劃的本質(zhì)是對(duì)集合進(jìn)行動(dòng)態(tài)規(guī)劃，對(duì)于給出的數(shù)據(jù)在某一個(gè)或幾個(gè)維度上一般具有比較小的范圍（可以枚舉一類的狀態(tài)），我們把一個(gè)枚舉出的狀態(tài)視為一個(gè)集合，通過它們之間的關(guān)系（產(chǎn)生式規(guī)則）可以進(jìn)行動(dòng)態(tài)規(guī)劃。當(dāng)集合中元素個(gè)數(shù)的不定性或范圍大時(shí)，如果直接開數(shù)組存，索引數(shù)組的編程復(fù)雜度太高（而且程序時(shí)間效率低下），所以要進(jìn)行集合編碼。一般利用數(shù)據(jù)的可枚舉性，采用進(jìn)位制的方法進(jìn)行狀態(tài)壓縮。下面舉一個(gè)經(jīng)典的問題作為例子：Noi2001 炮兵陣地【題目描述】司令部的將軍們打算在N*M的網(wǎng)格地圖上部署他們的炮兵部隊(duì)。一個(gè)N*M的地圖由N行M列組成，地圖的每一格可能是山地（用H 表示），也可能是平原（用P表示），如下圖。在每一格平原地形上最多可以布置一支炮兵部隊(duì)（山地上不能夠部署炮兵部隊(duì)）；一支炮兵部隊(duì)在地圖上的攻擊范圍如圖中黑色區(qū)域所示： 如果在地圖中的灰色所標(biāo)識(shí)的平原上部署一支炮兵部隊(duì)，則圖中的黑色的網(wǎng)格表示它能夠攻擊到的區(qū)域：沿橫向左右各兩格，沿縱向上下各兩格。圖上其它白色網(wǎng)格均攻擊不到。從圖上可見炮兵的攻擊范圍不受地形的影響。 現(xiàn)在，將軍們規(guī)劃如何部署炮兵部隊(duì)，在防止誤傷的前提下（保證任何兩支炮兵部隊(duì)之間不能互相攻擊，即任何一支炮兵部隊(duì)都不在其他支炮兵部隊(duì)的攻擊范圍內(nèi)），在整個(gè)地圖區(qū)域內(nèi)最多能夠擺放多少我軍的炮兵部隊(duì)?！据斎敫袷健?第一行包含兩個(gè)由空格分割開的正整數(shù)，分別表示N和M；接下來的N行，每一行含有連續(xù)的M個(gè)字符(39。P39?；蛘?9。H39。)，中間沒有空格。按順序表示地圖中每一行的數(shù)據(jù)。N≤100；M≤10?！据敵龈袷健?僅一行，包含一個(gè)整數(shù)K，表示最多能擺放的炮兵部隊(duì)的數(shù)量。【樣例輸入】 5 4PHPPPPHHPPPPPHPPPHHP【樣例輸出】 6 這是一道比較麻煩的問題，如果某點(diǎn)是P，就可以有放兵與不放兵兩種方案，但對(duì)于在I和J位置之前的所有P的擺放方案有多種方案，我們將這兩種方案分別去嘗試與P(I,J)之前所有方案結(jié)合，則P(I,J)又會(huì)有很多種方案。考慮一個(gè)列為10（M的最大值）的表。即使是一個(gè)全為P的空列上一共也只有60種合法的炮兵放置方法。具體對(duì)一個(gè)列數(shù)為10的PH表而言，對(duì)每一列也只有前兩列對(duì)其產(chǎn)生影響，我們?cè)O(shè)F[I,X,Y]來表示第I1行處于第X種狀態(tài)，第I行處于第Y種狀態(tài)時(shí)，從首行掃描到該行時(shí)所能存放的最多的炮兵數(shù)。則有F[I,X,Y] = Max{F[I1,Z,X] + N[Y]}，其中要求沒有互相攻擊的可能，N[Y]表示方案Y對(duì)應(yīng)的炮兵數(shù)。很多狀態(tài)壓縮動(dòng)態(tài)規(guī)劃是用二進(jìn)制存儲(chǔ)狀態(tài)，比如有1到10共10個(gè)點(diǎn)，需要把它們都走一遍，走過1,2,3點(diǎn)的路徑可以用[0000000111]2=[7]10表示，而走過1,2,3,5的路徑可以用[0000010111]2=[23]10表示。下面我們用位運(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)移。下面再舉一個(gè)例子：HCPC Spring 2007 FishCanFly【題目描述】fish is not a mon fish, he has a dream that he can fly someday. One day his friend wolfshow tells him a tale.It is said that there lives a magic bailey in the remote mountains. He can enable some fish to fly once a year. Every year many fish arrive at bailey39。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。s house. One can get some score when he enters it. But if you enter the same posthouse several times, you can get the score only once. You must remember that the total time is limited. So if you can39。t get there in time, you will lose it.Luckily, with another friend angela39。s help, fish gets the map. But he can39。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