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