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