【正文】 【問題描述】這些日子，F(xiàn)J的奶牛一共有P (1 ≤ P ≤ 300) 個待解決的問題。奶?，F(xiàn)在是上班族了，每個月的工資為M (1 ≤ M ≤ 1000) 。 奶?，F(xiàn)在需要雇人來解決那些問題，其中有一個專家非?？煽?，可以每一個月解決一個問題。他的收費方式是這樣子的：解決問題前后各付一次錢( 1 ≤ payment ≤ M ) ，當然奶牛必須在當時能夠支付足夠的錢。求解決這些問題所需要的最小時間。還有一點：這些問題是有嚴格先后順序的。【輸入格式】 第一行是兩個正整數(shù)M和P，以下P行每行兩個數(shù)，表示解決該問題前后分別需要付的費用?！据敵龈袷健?只有一個正整數(shù)即解決全部問題需要的最小月份數(shù)?！緲永斎搿?100 540 2060 2030 5030 5040 40【樣例輸出】 6【樣例說明】+++++++| | Avail | Probs | Before | After | Candy ||Month | Money | Solved | Payment | Payment | Money |+++++++| 1 | 0 | none | 0 | 0 | 0 || 2 | 100 | 1, 2 | 40+60 | 0 | 0 || 3 | 100 | 3, 4 | 30+30 | 20+20 | 0 || 4 | 100 | none | 0 | 50+50 | 0 || 5 | 100 | 5 | 40 | 0 | 60 || 6 | 100 | none | 0 | 40 | 60 | +++++++設F[X,Y]表示解決前X個問題且最后一個月解決了Y個問題所需要的最小月份數(shù)。利用輔助數(shù)組G1[X,Y]和G2[X,Y]表示在一個月解決問題X到問題Y間所有問題前后需要支付的費用。則有狀態(tài)轉移方程：F[I,J] = Min {F[K][I1] + P[I,J,K]}，其中G1[I,J] + G2[K,I1]不超過M時，P[I,J,K] = 1，否則P[I,J,K] = 2。這種算法的時間復雜度為O（N3）。和LIS一樣，可以加入貪心思想，如果設F[X]表示解決前X個問題需要的最小月份數(shù)，同時用輔助數(shù)組G[X]表示解決前X個問題取得最小月份時，該月最少花費的錢數(shù)。則有狀態(tài)轉移方程：F[I] = Min{F[J] + Q[J,I,G[X]]}，并隨時更新G[X]，則把時間復雜度降到了O（N2）。 樹型狀態(tài)劃分的動態(tài)規(guī)劃顧名思義，樹型狀態(tài)劃分的動態(tài)規(guī)劃就是在“樹”的數(shù)據(jù)結構上的動態(tài)規(guī)劃。由樹的結構可知，樹型動態(tài)規(guī)劃的方向一般是葉到根：將根的子節(jié)點傳遞有用的信息給根，使根得出最優(yōu)解。URAL1039 Anniversary【問題描述】有個公司要舉行一場晚會。為了能玩得開心，公司領導決定：如果邀請了某個人，那么一定不會邀請他的上司（上司的上司，上司的上司的上司……都可以邀請）。每個參加晚會的人都能為晚會增添一些氣氛，求一個邀請方案，使氣氛值的和最大?！据斎敫袷健?第1行一個整數(shù)N（1≤N≤6000）表示公司的人數(shù)。接下來N行每行一個整數(shù)。第i行的數(shù)表示第i個人的氣氛值x(128≤x≤127)。接下來每行兩個整數(shù)L，K。表示第K個人是第L個人的上司。輸入以0 0結束?！据敵龈袷健?只有一個數(shù)，最大的氣氛值和?！緲永斎搿?711111111 32 36 47 44 53 50 0【樣例輸出】 5 設F[I]表示邀請I的最大值，G[I]表示不邀請I的最大值。則F[I] = ∑{G[]},G[I] = ∑{Max(F[],G[]}}。大多的樹型動態(tài)規(guī)劃可以化成類似的類型，下面介紹一下多叉樹改造為二叉樹的方法。Ctsc1997 選課【問題描述】在大學里每個學生，為了達到一定的學分，必須從很多課程里選擇一些課程來學習，在課程里有些課程必須在某些課程之前學習，如高等數(shù)學總是在其它課程之前學習。現(xiàn)在有N門功課，每門課有個學分，每門課有一門或沒有直接先修課（若課程a是課程b的先修課即只有學完了課程a，才能學習課程b）。一個學生要從這些課程里選擇M門課程學習，問他能獲得的最大學分是多少？【輸入格式】 第一行有兩個整數(shù)N,M用空格隔開。(1≤N≤200,1≤M≤150)接下來的N行,第I+1行包含兩個整數(shù)ki和si, ki表示第I門課的直接先修課，si表示第I門課的學分。若ki=0表示沒有直接先修課（1≤ki≤N, 1≤si≤20）?！据敵龈袷健?只有一行，選M門課程的最大得分。【樣例輸入】 7 42 20 10 42 17 17 62 2【樣例輸出】 13以樣例數(shù)據(jù)為例，很容易建出一棵樹（如右圖所示）。我們可以選取某一個點K的條件只是它的父節(jié)點已經被選取或者它自己為根節(jié)點；而且我們不論如何取K的子孫節(jié)點，都不會影響到它父節(jié)點的選取情況，這滿足無后效性原則。我們用函數(shù)F[I,J]表示以第I個節(jié)點為父節(jié)點，取J個子節(jié)點的最佳代價，則可以進行動態(tài)規(guī)劃?？墒侨绱艘?guī)劃，其效率與搜索毫無差別。我們不妨改造樹，將其轉變?yōu)槎鏄?。變化方法為：一個節(jié)點的第一個孩子為其左孩子，而一個節(jié)點的兄弟為其右孩子。以樣例數(shù)據(jù)為例，建出一棵二叉樹（如右圖所示）。 轉化的時間復雜度為O（N）。我們還是利用同樣的狀態(tài)表示方法，則有狀態(tài)轉移方程：F[I,J] = Max（F[L,K] + F[R,JK1] + S[I], F[R,J]）整個算法的時間復雜度為O（N3）。 在實現(xiàn)樹型動態(tài)規(guī)劃的時候，通常使用后序遍歷。 填鴨 這里說的填鴨通常也被視為動態(tài)規(guī)劃，我們先來看一個經典的硬幣問題：給出N種硬幣的面值，問面值 M有多少種不同的表示方法。 我們常見的解法就是設F[I]表示面值為I的不同表示方法，則F[I] = ∑F[ICost[J]]。這種填鴨沒有決策，就是開一個大的數(shù)組，把代價值一個一個地填進去。 再舉一個簡單的游戲——步步為零。游戲者在一張菱形的表格中按照規(guī)則跳動，使得跳到的數(shù)字經過加號和減號的連接，盡可能的逼近零。游戲者從最下面的方格出發(fā)，按照每次可以往上面左右兩個格子的任意一格跳動，當游戲者跳到最頂端的方格時，游戲結束。在游戲未結束前，游戲者不允許跳到表格外。 2 3 1 3 5 7 6 10 2 20 7 5 –8 10 8 7對于上面的表格，最好的跳動方案是：7+8+(5)+(2)512=0或7+10+(7)6+(3)3+2=0或7+10+(5)105+1+2=0或7+10+(5)+(2)532=0。利用填鴨的方法，設F[I,J,K]表示到第I層第J個數(shù)字組成K的可能性，則有F[I,J,K] = F[I + 1,J 1,K + A[I,J]] or F[I + 1,J 1,K A[I,J]] or F[I + 1,J,K + A[I,J]] or F[I + 1,J,K A[I,J]]。Oibh2005 胖子三角【問題描述】最近，地球上興起了一股“登月熱”。人們紛紛報名參加太空游。胖子這個摩登青年當然不會落伍?，F(xiàn)在，胖子乘神州X號來到月球，準備開辟一片新的天地。他在月球上建立了一個食堂，并且想給他的月球食堂建造一個圍欄。路人皆知的是胖子很愛吃，而且胖子很虛榮，為了使圍欄看起來很酷，而且很像麥當勞的珍寶三角，胖子決定用面包把它建成三角形。胖子現(xiàn)在擁有N(3=N40)塊面包，由于胖子在建造圍欄時不由自主地吃掉了一部分，所以這些面包長短不一，但胖子還算有些人性，將每塊長度都吃成了整數(shù)，經過alston銳利的目光推測，將每塊面包長度(1=L40)看出，為天文學愛好者帶來極大方便。由于胖子的占有欲一般都很強(特別是對食物)，所以他還想用所有的面包使圍欄的面積最大?！据斎敫袷健?第一行有一個整數(shù)N，第二行有N個數(shù)，表示面包的長度?！据敵龈袷健?只有一個數(shù)，即最大面積，保留兩位小數(shù)。【樣例輸入】 34 3 5【樣例輸出】 6每一個面包可以被包含在三條邊中的任意一條邊中，設F[I,J,K]表示用前I個面包組成一條長度為J的邊和一條長度為K的邊的可能性，則有狀態(tài)轉移方程：F[I,J,K] = F[I1,JAI,K] or F[I1,J,KAI]。最后枚舉一下組成的可能所有三角型，取其中面積最大的?？偟臅r間復雜度為O（N3L2）。NEYCoi 2003 搭建雙塔【題目描述】2001年9月11日，一場突發(fā)的災難將紐約世界貿易中心大廈夷為平地，Mr. F曾親眼目睹了這次災難。為了紀念“”事件，Mr. F決定自己用水晶來搭建一座雙塔?！　r. F有N塊水晶，每塊水晶有一個高度，他想用這N塊水晶搭建兩座有同樣高度的塔，使他們成為一座雙塔，Mr. F可以從這N塊水晶中任取M（1≤M≤N）塊來搭建。但是他不知道能否使兩座塔有同樣的高度，也不知道如果能搭建成一座雙塔，這座雙塔的最大高度是多少。所以他來請你幫忙。給定水晶的數(shù)量N（1≤N≤100）和每塊水晶的高度Hi（N塊水晶高度的總和不超過2000），你的任務是判斷Mr. F能否用這些水晶搭建成一座雙塔（兩座塔有同樣的高度），如果能，則輸出所能搭建的雙塔的最大高度，否則輸出“Impossible”?！据斎敫袷健?輸入的第一行為一個數(shù)N，表示水晶的數(shù)量。第二行為N個數(shù)，第i個數(shù)表示第i個水晶的高度?！据敵龈袷健?輸出僅包含一行，如果能搭成一座雙塔，則輸出雙塔的最大高度，否則輸出一個字符串“Impossible”。【樣例輸入】 51 2 4 3 5【樣例輸出】 7 最基本的方法還是填鴨，設F[I,J,K]表示用前I個水晶組成一塔高度為J另一塔高度為K的可能性，則有狀態(tài)轉移方程：F[I,J,K] = F[I1,JAI,K] or F[I1,J,KAI] or F[I1,J,K]。時間復雜度為O（N3H2）。 實際上，如果設F[I,J]表示用前I個水晶組成一對高度差為J的較低塔的最高高度，就可以把時間復雜度降為O（N2）。 排序 排序是一件利器，經常被使用在加入貪心思想的動態(tài)規(guī)劃問題當中，通過也會出現(xiàn)在避免出現(xiàn)重復的問題當中，貪心思想的例子前面說過了很多，下面將舉例說明排序在動態(tài)規(guī)劃問題中的應用。GYoi 2007 購物計劃【題目描述】寧寧利用假期打工賺了一大筆錢，這使得她非常想上街進行一次大采購。寧寧有個壞習慣，看到東西就想買。阿月為此傷透了腦筋，最后他決定為寧寧來計劃先買哪些東西后買哪些東西，以此來為寧寧省錢。寧寧也很心疼自己的錢，于是決定按照阿月的計劃來安排買東西的先后順序，但是有一點可以肯定：只要她口袋里的錢數(shù)不低于m元就要繼續(xù)買東西。阿月需要你的幫助，他希望寧寧最后剩下的錢越多越好?！据斎敫袷健?輸入第一行包括三個正整數(shù)n，m和s（n≤100，0≤m,s≤10000），表示街上出售的商品共有n種，而寧寧口袋里最初有s元錢。第二行包含n個用空格分隔的不超過1000的正整數(shù)，表示對應商品的價格。【輸出格式】 輸出只包含一個非負整數(shù)t，即寧寧最后能剩下的最大錢數(shù)?！緲永斎搿? 5 102 7 4 2【樣例輸出】4【樣例說明】 阿月要求寧寧先買商品1和商品3之后，寧寧只剩下4元錢，低于m = 5元，于是停止購物，最后剩下4元。 寧寧停止購物有兩種情況：錢數(shù)低于m元或者沒有東西可買。第一種情況用填鴨的方法可以輕松解決。而第二種情況則需要提前判斷，如何判斷買過一些東西之后什么都買不起了呢？為了保證買不起A[I]時，A[I+1..N]也都買不起，需要把商品的價值從小到大排序，從小的開始買，累和為t，滿足stA[I]時，就什么也買不起了。 是否可能不是從小連續(xù)的購買方法也會導致什么也買不起了呢？假設這樣是可以的，那么其肯定不是最優(yōu)解（證明很簡單），不必考慮。Greater NewYork 2006 Margaritas on the River Walk【題目描述】有幾種不同價格的瑪格麗塔酒，給你一定的錢，讓你去買酒。規(guī)定每種酒只能買一瓶，而且要買到你沒有足夠的錢去買其它的酒為止。問總共有多少種不同的購買方案。例如，你有25元錢，有六種酒，價格如下Vendor A B C D H J Price 8 9 8 7 16 5 可能的購買方案有 ABC(25), ABD(24), ABJ(22), ACD(23), ACJ(21), ADJ( 20), AH(24), BCD(24), BCJ(22), BDJ(21), BH(25), CDJ(20), CH(24), DH(23) HJ(21) 共15種方案?！据斎敫袷健?第一行包括兩個正整數(shù)N和V，表示酒的種類和持有的錢數(shù)，接下來一行包含N個正整數(shù)表