【正文】 【輸入格式】 第一行包括兩個正整數(shù)N和V，表示酒的種類和持有的錢數(shù)，接下來一行包含N個正整數(shù)表示每。問總共有多少種不同的購買方案。Greater NewYork 2006 Margaritas on the River Walk【題目描述】有幾種不同價格的瑪格麗塔酒，給你一定的錢，讓你去買酒。而第二種情況則需要提前判斷，如何判斷買過一些東西之后什么都買不起了呢？為了保證買不起A[I]時，A[I+1..N]也都買不起，需要把商品的價值從小到大排序，從小的開始買，累和為t，滿足stA[I]時，就什么也買不起了。 寧寧停止購物有兩種情況：錢數(shù)低于m元或者沒有東西可買?！据敵龈袷健?輸出只包含一個非負(fù)整數(shù)t，即寧寧最后能剩下的最大錢數(shù)?！据斎敫袷健?輸入第一行包括三個正整數(shù)n，m和s（n≤100，0≤m,s≤10000），表示街上出售的商品共有n種，而寧寧口袋里最初有s元錢。寧寧也很心疼自己的錢，于是決定按照阿月的計劃來安排買東西的先后順序，但是有一點(diǎn)可以肯定：只要她口袋里的錢數(shù)不低于m元就要繼續(xù)買東西。寧寧有個壞習(xí)慣，看到東西就想買。 排序 排序是一件利器，經(jīng)常被使用在加入貪心思想的動態(tài)規(guī)劃問題當(dāng)中，通過也會出現(xiàn)在避免出現(xiàn)重復(fù)的問題當(dāng)中，貪心思想的例子前面說過了很多，下面將舉例說明排序在動態(tài)規(guī)劃問題中的應(yīng)用。時間復(fù)雜度為O（N3H2）?！据敵龈袷健?輸出僅包含一行，如果能搭成一座雙塔，則輸出雙塔的最大高度，否則輸出一個字符串“Impossible”?！据斎敫袷健?輸入的第一行為一個數(shù)N，表示水晶的數(shù)量。所以他來請你幫忙?！　r. F有N塊水晶，每塊水晶有一個高度，他想用這N塊水晶搭建兩座有同樣高度的塔，使他們成為一座雙塔，Mr. F可以從這N塊水晶中任取M（1≤M≤N）塊來搭建。NEYCoi 2003 搭建雙塔【題目描述】2001年9月11日，一場突發(fā)的災(zāi)難將紐約世界貿(mào)易中心大廈夷為平地，Mr. F曾親眼目睹了這次災(zāi)難。最后枚舉一下組成的可能所有三角型，取其中面積最大的。【輸出格式】 只有一個數(shù)，即最大面積，保留兩位小數(shù)。由于胖子的占有欲一般都很強(qiáng)(特別是對食物)，所以他還想用所有的面包使圍欄的面積最大。路人皆知的是胖子很愛吃，而且胖子很虛榮，為了使圍欄看起來很酷，而且很像麥當(dāng)勞的珍寶三角，胖子決定用面包把它建成三角形?，F(xiàn)在，胖子乘神州X號來到月球，準(zhǔn)備開辟一片新的天地。人們紛紛報名參加太空游。利用填鴨的方法，設(shè)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]]。在游戲未結(jié)束前，游戲者不允許跳到表格外。游戲者在一張菱形的表格中按照規(guī)則跳動，使得跳到的數(shù)字經(jīng)過加號和減號的連接，盡可能的逼近零。這種填鴨沒有決策，就是開一個大的數(shù)組，把代價值一個一個地填進(jìn)去。 填鴨 這里說的填鴨通常也被視為動態(tài)規(guī)劃，我們先來看一個經(jīng)典的硬幣問題：給出N種硬幣的面值，問面值 M有多少種不同的表示方法。我們還是利用同樣的狀態(tài)表示方法，則有狀態(tài)轉(zhuǎn)移方程：F[I,J] = Max（F[L,K] + F[R,JK1] + S[I], F[R,J]）整個算法的時間復(fù)雜度為O（N3）。以樣例數(shù)據(jù)為例，建出一棵二叉樹（如右圖所示）。我們不妨改造樹，將其轉(zhuǎn)變?yōu)槎鏄?。我們用函?shù)F[I,J]表示以第I個節(jié)點(diǎn)為父節(jié)點(diǎn)，取J個子節(jié)點(diǎn)的最佳代價，則可以進(jìn)行動態(tài)規(guī)劃?！緲永斎搿?7 42 20 10 42 17 17 62 2【樣例輸出】 13以樣例數(shù)據(jù)為例，很容易建出一棵樹（如右圖所示）。若ki=0表示沒有直接先修課（1≤ki≤N, 1≤si≤20）。一個學(xué)生要從這些課程里選擇M門課程學(xué)習(xí)，問他能獲得的最大學(xué)分是多少？【輸入格式】 第一行有兩個整數(shù)N,M用空格隔開。Ctsc1997 選課【問題描述】在大學(xué)里每個學(xué)生，為了達(dá)到一定的學(xué)分，必須從很多課程里選擇一些課程來學(xué)習(xí)，在課程里有些課程必須在某些課程之前學(xué)習(xí)，如高等數(shù)學(xué)總是在其它課程之前學(xué)習(xí)。則F[I] = ∑{G[]},G[I] = ∑{Max(F[],G[]}}?！据敵龈袷健?只有一個數(shù)，最大的氣氛值和。表示第K個人是第L個人的上司。第i行的數(shù)表示第i個人的氣氛值x(128≤x≤127)?！据斎敫袷健?第1行一個整數(shù)N（1≤N≤6000）表示公司的人數(shù)。為了能玩得開心，公司領(lǐng)導(dǎo)決定：如果邀請了某個人，那么一定不會邀請他的上司（上司的上司，上司的上司的上司……都可以邀請）。由樹的結(jié)構(gòu)可知，樹型動態(tài)規(guī)劃的方向一般是葉到根：將根的子節(jié)點(diǎn)傳遞有用的信息給根，使根得出最優(yōu)解。則有狀態(tài)轉(zhuǎn)移方程：F[I] = Min{F[J] + Q[J,I,G[X]]}，并隨時更新G[X]，則把時間復(fù)雜度降到了O（N2）。這種算法的時間復(fù)雜度為O（N3）。利用輔助數(shù)組G1[X,Y]和G2[X,Y]表示在一個月解決問題X到問題Y間所有問題前后需要支付的費(fèi)用?！据敵龈袷健?只有一個正整數(shù)即解決全部問題需要的最小月份數(shù)。還有一點(diǎn)：這些問題是有嚴(yán)格先后順序的。他的收費(fèi)方式是這樣子的：解決問題前后各付一次錢( 1 ≤ payment ≤ M ) ，當(dāng)然奶牛必須在當(dāng)時能夠支付足夠的錢。奶?，F(xiàn)在是上班族了，每個月的工資為M (1 ≤ M ≤ 1000) 。數(shù)組G需要遞推，總體算法的時間復(fù)雜度為O（N3）。一定要注意：所有字母在鍵盤上的排列順序是不能改變的?！据敵鑫募枯敵霭ㄒ粋€整數(shù)S。較大的數(shù)字表示較高的使用頻率。K表示提供按鍵的個數(shù)，L表示有多少字符需要安排到鍵盤上。不過你可以安排任意數(shù)量的字母對應(yīng)一個按鍵。而我們需要你編寫一個程序，找到一種最優(yōu)的鍵盤（對于給定的字母使用頻率）。有些字母的使用頻率要高些，但它們被安排在一組字母的第3個或第4個。每個鍵可以對應(yīng)一組字母。 其他二維狀態(tài)劃分的動態(tài)規(guī)劃舉例Central European 2000 IKeyBoard【問題描述】移動電話用戶都對使用電話鍵盤輸入英文短消息感到煩透了。【輸出文件】輸出包括一個整數(shù)k，表示消除整個串最少需要放入k個球?！据斎胛募枯斎氲牡谝恍惺且粋€整數(shù)n（1 ≤ n ≤ 100），表示初始的球數(shù)。舉個n=12的時候的例子，整個串的消除過程如下：第一步，在第四個球前加入一個藍(lán)色球；第二步，在第八個球前加入一個藍(lán)色球；第三步，在第八個球前加入一個藍(lán)色球；第四步，在第二個球前加入一個綠色球；第五步，在第二個球前加入一個綠色球；第六步，在第一個球前加入一個紅色球。龍珠的規(guī)則是這樣的：有一串n個帶顏色的球（最多可能有紅、黃、藍(lán)和綠四種顏色），你可以向這個串里加球，當(dāng)有連續(xù)三個或三個以上相同顏色的球連在一起時，我們稱為可消除狀態(tài)，通過一次加球新產(chǎn)生出的可消除狀態(tài)才真正意義上的可消除。設(shè)F[I,J]表示表達(dá)式從I到J部分的最大值，G[I,J] 表示表達(dá)式從I到J部分的最小值，則有： Sign[i] = ‘*’時F[I,J] = Max{F[I,K] * F[K+1,J], G[I,K] * F[K+1,J], F[I,K] * G[K+1,J], G[I,K] * G[K+1,J]}G[I,J] = Min{F[I,K] * F[K+1,J], G[I,K] * F[K+1,J], F[I,K] * G[K+1,J], G[I,K] * G[K+1,J]}Sign[i] = ‘+’時F[I,J] = Max{F[I,K] + F[K+1,J]}G[I,J] = Min{G[I,K] + G[K+1,J]}AsyzOI 2005龍珠外掛【問題描述】龍珠是騰訊公司新推出的一個游戲項(xiàng)目。【輸出格式】 只有一個正整數(shù)即表達(dá)式可以到達(dá)的最大值。實(shí)際上，9也是最大的結(jié)果。所以我們不如將原串復(fù)制一份加到原串的后面再進(jìn)行動態(tài)規(guī)劃。計算F[I,J]時，只會用到含有能量珠數(shù)目比它少的串在數(shù)組中的值，所以要按照串的能量珠數(shù)目依次增大的順序遞推。設(shè)F[I,J]為從以A[I]為首標(biāo)記的能量珠開始順時針數(shù)到以A[J]為尾標(biāo)記的能量珠為止所有能量珠組成的串合并后放出的最大能量?！据敵龈袷健?只有一個正整數(shù)E（E≤*109），為一個最優(yōu)聚合順序所釋放的總能量。第N顆珠子的尾標(biāo)記應(yīng)該等于第1顆珠子的頭標(biāo)記。第二行是N個用空格隔開的正整數(shù)，所有的數(shù)均不超過1000。這一串項(xiàng)鏈可以得到最優(yōu)值的一個聚合順序所釋放的總能量為((4⊕1)⊕2)⊕3）=10*2*3+10*3*5+10*5*10=710。我們用記號⊕表示兩顆珠子的聚合操作，(j⊕k)表示第j，k兩顆珠子聚合后所釋放的能量。顯然，不同的聚合順序得到的總能量是不同的，請你設(shè)計一個聚合順序，使一串項(xiàng)鏈釋放出的總能量最大。如果前一顆能量珠的頭標(biāo)記為m，尾標(biāo)記為r，后一顆能量珠的頭標(biāo)記為r，尾標(biāo)記為n，則聚合后釋放的能量為（Mars單位），新產(chǎn)生的珠子的頭標(biāo)記為m，尾標(biāo)記為n。并且，對于相鄰的兩顆珠子，前一顆珠子的尾標(biāo)記一定等于后一顆珠子的頭標(biāo)記。在項(xiàng)鏈上有N顆能量珠。 另外一個經(jīng)典的二維狀態(tài)劃分的動態(tài)規(guī)劃為矩陣乘法，而OIers則更習(xí)慣稱之為石子和并或者最小代價子母樹。實(shí)際上計算某個狀態(tài)集合，其實(shí)質(zhì)是計算這個集合中狀態(tài)值最大的狀態(tài)，因此我們只需知道這個集合中的最大狀態(tài)值就足夠了。該算法的時間復(fù)雜度為O（N4）。對于LCIS的定義如下：給出兩個長度分別為n,m的序列A和B。和合唱隊型類似，不要先枚舉分割點(diǎn)，將原串和其逆串的最長公共子序列的最長公共子序列計算之后再做分割處理?！据敵龈袷健?只有一個正整數(shù)，為將給定字符串變成回文詞所需要插入的最少字符數(shù)。你的任務(wù)是求出將給定字符串變成回文詞所需要插入的最少字符數(shù)。Ioi2000 Palindrome【題目描述】回文詞是一種對稱的字符串——也就是說，一個回文詞從左向右讀和從右向左讀得到的結(jié)果是一樣的。F[I,J]表示第1個字符串前I個字符和第2個字符串前J個字符的最長公共子序列的長度，則有狀態(tài)轉(zhuǎn)移方程：F[I,J] = F[I1,J1] + 1, 其中A[I] = B[J]；F[I,J] = F[I1,J1], 其中A[I] B[J]；計算LCS長度的時間復(fù)雜度：O（LEN_ALCS問題就是要求兩個給定字符串的最長公共子序列的長度。將兩個給定字符串分別刪去零個或多個字符后得到的長度最長的相同字符序列。 典型的二維狀態(tài)劃分的動態(tài)規(guī)劃 下面我們開始討論二維狀態(tài)劃分的動態(tài)規(guī)劃，這類題目需要使用兩個變量確定一個狀態(tài)的階段。(S^(1I)) == 1。t arrive in time no matter which path he takes, just ouput Miss bailey!. See the examples for further clarification.【樣例輸入】 30 2 0 0 02 0 3 0 00 3 0 8 10 0 8 0 00 0 1 0 01 2 3【樣例輸出】 Fish can fly! 6 首先利用Floyed求出最短路，然后進(jìn)行狀態(tài)壓縮的動態(tài)規(guī)劃。s house is at place n+1. The next line contains n integers which indicate the scores at each posthouse. Then followes an integer number denoting the time limit.【輸出格式】 If fish can arrive at bailey39。s help, fish gets the map. But he can39。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。下面再舉一個例子：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。很多狀態(tài)壓縮動態(tài)規(guī)劃是用二進(jìn)制存儲狀態(tài)，比如有1到10共10個點(diǎn)，需要把它們都走一遍，走過1,2,3點(diǎn)的路徑可以用[0000000111]2=[7]10表示，而走過1,2,3,5的路徑可以用[0000010111]2=[23]10表示。具體對一個列數(shù)為10的PH表而言，對每一列也只有前兩列對其產(chǎn)生影響，我們設(shè)F[I,X,Y]來表示第I1行處于第X種狀態(tài)，第I行處于第Y種狀態(tài)時，從首行掃描到該行時所能存放的最多的炮兵數(shù)。考慮一個列為10（M的最大值）的表?！据敵龈袷健?僅一行，包含