信息學(xué)奧賽中的動(dòng)態(tài)規(guī)劃教學(xué)課件

1、動(dòng)態(tài)規(guī)劃講稿1動(dòng)態(tài)規(guī)劃講稿1數(shù)字三角形IOI19942數(shù)字三角形IOI19942題目描述 Description 如圖所示的數(shù)字三角形，從頂部出發(fā)，在每一結(jié)點(diǎn)可以選擇向左走或得向右走，一直走到底層，要求找出一條路徑，使路徑上的值最大。輸入描述 Input Description 第一行是數(shù)塔層數(shù)N(1=N=100)。第二行起，按數(shù)塔圖形，有一個(gè)或多個(gè)的整數(shù)，表示該層節(jié)點(diǎn)的值，共有N行。輸出描述 Output Description 輸出最大值。樣例輸入 Sample Input 5 13 11 8 12 7266 14 15 812 7 13 24 11樣例輸出 Sample Output 8

2、63題目描述 Description 3解法1：暴搜DFS一遍遍歷整個(gè)數(shù)字三角形，對(duì)于每個(gè)節(jié)點(diǎn)，我們有2個(gè)選擇，那么，n層的數(shù)字三角形有2n種可能，所以時(shí)間復(fù)雜度為O(2n)T L E！4解法1：暴搜DFS一遍遍歷整個(gè)數(shù)字三角形，對(duì)于每個(gè)節(jié)點(diǎn)，我們解法2：貪心一路下去只找最大的可以嗎？W A !5解法2：貪心一路下去只找最大的可以嗎？W A !5解法3：最長(zhǎng)路將整個(gè)數(shù)字三角形看作一個(gè)由點(diǎn)和邊組成的圖，以a11為起點(diǎn)，求它到ani(1=i=n)的最長(zhǎng)路Dijkstra算法：本題部分?jǐn)?shù)據(jù)有負(fù)值SPFA算法：O(kM)的話(huà)應(yīng)該能行Bellman-Ford算法：O(VE)有點(diǎn)危險(xiǎn)啊Floyd算法：O(

3、n3)你確定要用嗎？方法可行但是打起來(lái)好麻煩6解法3：最長(zhǎng)路將整個(gè)數(shù)字三角形看作一個(gè)由點(diǎn)和邊組成的圖，以a還有什么更好的算法嗎？當(dāng)然有！那就是本課要講的內(nèi)容動(dòng)態(tài)規(guī)劃7還有什么更好的算法嗎？當(dāng)然有！那就是本課要講的內(nèi)容動(dòng)態(tài)規(guī)分析這個(gè)數(shù)字三角形，我們可以發(fā)現(xiàn)：一個(gè)節(jié)點(diǎn)只會(huì)受到上面兩個(gè)節(jié)點(diǎn)的值的影響，而上面節(jié)點(diǎn)的值也只會(huì)受到更加上面的節(jié)點(diǎn)的值的影響由此可寫(xiě)出遞歸式dpij=max(dpi-1j,dpi-1j-1)+aij上面這個(gè)遞歸式在動(dòng)態(tài)規(guī)劃中被叫做狀態(tài)轉(zhuǎn)移方程式，根據(jù)這個(gè)式子，我們可以從dp11開(kāi)始遞推，直到數(shù)字三角形的最后一行。時(shí)間復(fù)雜度O(n2)，完全無(wú)壓力8分析這個(gè)數(shù)字三角形，我們可以發(fā)現(xiàn)

4、：一個(gè)節(jié)點(diǎn)只會(huì)受到上面兩個(gè)節(jié)動(dòng)態(tài)規(guī)劃是優(yōu)美的動(dòng)態(tài)規(guī)劃是神奇的動(dòng)態(tài)規(guī)劃是有趣的動(dòng)態(tài)規(guī)劃是簡(jiǎn)單的動(dòng)態(tài)規(guī)劃是卡騙分的動(dòng)態(tài)規(guī)劃是禁貪心的動(dòng)態(tài)規(guī)劃是防止爆0 的動(dòng)態(tài)規(guī)劃最簡(jiǎn)單最好玩了我最喜歡動(dòng)態(tài)規(guī)劃了！什么鬼！9動(dòng)態(tài)規(guī)劃是優(yōu)美的什么鬼！90-1背包問(wèn)題Merkel and Hellman 1978NOIP2005普及組100-1背包問(wèn)題Merkel and Hellman 19題目描述 Description 由于該題目的題目描述版本過(guò)多，不再描述輸入描述 Input Description 輸入第一行有兩個(gè)整數(shù)T（1=T=1000）和M（1=M=100），用一個(gè)空格隔開(kāi)，T代表最大重量，M代表物品的數(shù)

5、目。接下來(lái)的M行每行包括兩個(gè)在1到100之間（包括1和100）的整數(shù)，分別表示采摘某個(gè)物品的時(shí)間和每個(gè)物品的價(jià)值。輸出描述 Output Description 輸出包括一行，這一行只包含一個(gè)整數(shù)，表示在不超過(guò)規(guī)定重量的情況下，可以拿到的最大價(jià)值。樣例輸入 Sample Input 1 11 1樣例輸出 Sample Output 1數(shù)據(jù)范圍及提示 Data Size & Hint 【數(shù)據(jù)規(guī)?！繉?duì)于30%的數(shù)據(jù)，M=10；對(duì)于全部的數(shù)據(jù)，M=100。11題目描述 Description 11老規(guī)矩：暴搜TLE貪心一定WA最短路你可以試試怎么辦？12老規(guī)矩：12動(dòng)態(tài)規(guī)劃才是王道！我們先分析下暴搜

6、的過(guò)程：我們對(duì)每個(gè)物品進(jìn)行了搜索，產(chǎn)生了大量的狀態(tài)，每個(gè)狀態(tài)包括三個(gè)要點(diǎn)：1.目前已用的背包的容量，這個(gè)不用多說(shuō)2.目前已經(jīng)獲得的價(jià)值，這個(gè)也不用多說(shuō)3.目前已經(jīng)處理了多少物品，記錄下已經(jīng)處理物品數(shù)量的原因是由于每個(gè)物品只能拿一個(gè)，所以要記錄下已經(jīng)處理了多少物品，防止以后重復(fù)處理有什么想法沒(méi)？13動(dòng)態(tài)規(guī)劃才是王道！我們先分析下暴搜的過(guò)程：有什么想法沒(méi)？13為什么不記錄下相同的狀態(tài)時(shí)的最優(yōu)策略呢？14為什么不記錄下相同的狀態(tài)時(shí)的最優(yōu)策略呢？14在使用相同的容量和處理了相同的物品后，剩下的搜索過(guò)程應(yīng)該是相同的，假如共有n個(gè)物品，我們已經(jīng)處理了m個(gè)，那么還需要處理的物品數(shù)量就是n-m，但是在背包剩余

7、體積為v的情況下，剩下n-m個(gè)物品產(chǎn)生的最優(yōu)解應(yīng)該是相同的，這樣就可以簡(jiǎn)化搜索過(guò)程，但是前面的怎么辦呢？前面的當(dāng)然要最好的！于是，我們得到一條結(jié)論：在其他狀態(tài)均相同的情況下，選擇最好的總是對(duì)的！所以，我們可以開(kāi)始優(yōu)化這個(gè)搜索了：每次搜索到一個(gè)狀態(tài)，就從之前搜到過(guò)的狀態(tài)里找一遍，如果看見(jiàn)可以替換的狀態(tài)就更新眾：你不覺(jué)得更慢了么所以，怎么辦呢？15在使用相同的容量和處理了相同的物品后，剩下的搜索過(guò)程應(yīng)該是相你還記的桶排序嗎？直接用數(shù)組下標(biāo)記錄，時(shí)間復(fù)雜度O(1)這個(gè)可以這樣做嗎？沒(méi)問(wèn)題！看數(shù)據(jù)范圍：1=T=1000，1=M=100，狀態(tài)只需要記錄下重量和已處理的物品數(shù)，空間復(fù)雜度O(TM)，128

8、MB內(nèi)存沒(méi)問(wèn)題至于狀態(tài)轉(zhuǎn)移方程式的話(huà)：dpij=max(dpi-1j,dpi-1j-vi+ci)我一般習(xí)慣寫(xiě)成：dpi+1j=max(dpij,dpi+1j)dpi+1j+vi=max(dpi+1j+vi,dpij+ci)這個(gè)看個(gè)人喜好就可以了，沒(méi)有強(qiáng)制要求的處理時(shí)，只要for一遍，把數(shù)組填充好就可以啦，時(shí)間復(fù)雜度O(TM)P.S.：這字母是誰(shuí)規(guī)定的，這么惡心16你還記的桶排序嗎？直接用數(shù)組下標(biāo)記錄，時(shí)間復(fù)雜度O(1)16如果卡你空間怎么辦？17如果卡你空間怎么辦？17滾蛋動(dòng)數(shù)組你還記得斐波那契問(wèn)題怎么做的嗎？c=a+b a=b b=c根本不用開(kāi)一個(gè)數(shù)組嘛！這個(gè)問(wèn)題也一樣，除了前一行，其他的狀

9、態(tài)根本就用不到嘛！那么：要你何用！18滾蛋動(dòng)數(shù)組你還記得斐波那契問(wèn)題怎么做的嗎？要你何用！18也就是說(shuō)，數(shù)組只留2行就可以了，每處理完一行，就把第二行的結(jié)果放回第一行，繼續(xù)處理滾動(dòng)數(shù)組是用時(shí)間換空間的一種策略有沒(méi)有更好的方法呢？19也就是說(shuō)，數(shù)組只留2行就可以了，每處理完一行，就把第二行的結(jié)背包問(wèn)題可以用一維數(shù)組解決你造嗎？由于重量沒(méi)有負(fù)數(shù)，所以可以直接向后轉(zhuǎn)移，而且不用向下轉(zhuǎn)移了，但這樣就有可能重復(fù)處理一個(gè)物品，怎么辦？很簡(jiǎn)單，改變下方向，從后往前處理就可以啦至此，01背包完滿(mǎn)完成20背包問(wèn)題可以用一維數(shù)組解決你造嗎？20難度增加的背包問(wèn)題更加喜(sang)聞(xin)樂(lè)(bing)見(jiàn)(ku

10、ang)的背包問(wèn)題21難度增加的背包問(wèn)題更加喜(sang)聞(xin)樂(lè)(bing超大背包問(wèn)題每個(gè)物品只能拿一次，物品數(shù)量M=100，背包容量T=109，每個(gè)物品的價(jià)值=100，每個(gè)物品的重量=109由于本題物品的價(jià)值非常小，所以可以將dp數(shù)組改為由已處理的物品數(shù)量和價(jià)值，數(shù)組內(nèi)存儲(chǔ)內(nèi)容改為當(dāng)前所需的重量即可22超大背包問(wèn)題每個(gè)物品只能拿一次，物品數(shù)量M=100，背包容二維背包問(wèn)題對(duì)于每個(gè)物品，分別有體積v和重量w，求體積和重量均不超標(biāo)的情況下可以拿到的最大價(jià)值維數(shù)改為三維，改變下轉(zhuǎn)移，也可簡(jiǎn)化為二維，從后往前for得出正確答案23二維背包問(wèn)題對(duì)于每個(gè)物品，分別有體積v和重量w，求體積和重量完

11、全背包問(wèn)題每個(gè)物品可以拿無(wú)限次，只要不超過(guò)最大重量即可24完全背包問(wèn)題每個(gè)物品可以拿無(wú)限次，只要不超過(guò)最大重量即可24思路1：背包+枚舉在狀態(tài)轉(zhuǎn)移時(shí)枚舉每個(gè)物品可以拿的次數(shù)，時(shí)間復(fù)雜度O(VNK)25思路1：背包+枚舉在狀態(tài)轉(zhuǎn)移時(shí)枚舉每個(gè)物品可以拿的次數(shù)，時(shí)間優(yōu)化1：減少物品種類(lèi)對(duì)于一個(gè)物品來(lái)說(shuō)，假如它的重量大于等于另一個(gè)物品且它的價(jià)值比另一個(gè)物品低，那么要它何用？可以直接省略掉該物品，所以只要先預(yù)對(duì)所有物品進(jìn)行一遍O(n2)的預(yù)處理，就能帶來(lái)很大的優(yōu)化26優(yōu)化1：減少物品種類(lèi)對(duì)于一個(gè)物品來(lái)說(shuō)，假如它的重量大于等于另優(yōu)化2：轉(zhuǎn)化為0-1背包將一個(gè)物品看成多個(gè)物品，時(shí)間復(fù)雜度沒(méi)有發(fā)生變化但是大家

12、記得一個(gè)叫做鬼谷子的錢(qián)袋的題嗎？如一個(gè)物品最多可以拿10個(gè)，則可以拆分成：1個(gè)該物品，2個(gè)該物品，3個(gè)該物品，4個(gè)該物品，達(dá)到log(k)的級(jí)別，也是個(gè)不錯(cuò)的優(yōu)化27優(yōu)化2：轉(zhuǎn)化為0-1背包將一個(gè)物品看成多個(gè)物品，時(shí)間復(fù)雜度沒(méi)思路2：用一維背包解決大家還記得一維的背包解決方案嗎？此題也可，只不過(guò)為了使一個(gè)物品可以重復(fù)計(jì)算，只需要將從后往前改為從前往后即可，時(shí)間復(fù)雜度O(VN)28思路2：用一維背包解決大家還記得一維的背包解決方案嗎？此題也多重背包問(wèn)題對(duì)于每個(gè)物品，可以拿不同的次數(shù)，如：有的1次，有的10次，有的100次依然采取之前的二進(jìn)制思想，簡(jiǎn)化問(wèn)題29多重背包問(wèn)題對(duì)于每個(gè)物品，可以拿不同的

13、次數(shù)，如：有的1次，有混合背包問(wèn)題對(duì)于一個(gè)背包問(wèn)題，有多種物品可以選擇：有只能拿一件的，有可以拿多個(gè)的，有可以無(wú)限拿的，這時(shí)候應(yīng)該怎么辦？30混合背包問(wèn)題對(duì)于一個(gè)背包問(wèn)題，有多種物品可以選擇：有只能拿一這個(gè)問(wèn)題綜合了三種背包，代表這個(gè)問(wèn)題可以使用各種背包問(wèn)題的優(yōu)化方法！31這個(gè)問(wèn)題綜合了三種背包，代表這個(gè)問(wèn)題可以使用各種背包問(wèn)題的優(yōu)優(yōu)化1采用完全背包問(wèn)題的優(yōu)化方式1，即可瞬間去除大量無(wú)用物品P.S.:簡(jiǎn)直就是個(gè)垃圾清理器32優(yōu)化1采用完全背包問(wèn)題的優(yōu)化方式1，即可瞬間去除大量無(wú)用物品優(yōu)化2先不考慮多重背包，只考慮01背包和完全背包，那么，就可以用喜聞樂(lè)見(jiàn)的一維數(shù)組方法求解，只要在轉(zhuǎn)移前判斷下是

14、從前往后還是從后往前轉(zhuǎn)移就行了，那么多重背包怎么辦？笨！用二進(jìn)制轉(zhuǎn)成多個(gè)01背包啊！33優(yōu)化2先不考慮多重背包，只考慮01背包和完全背包，那么，就可金明的預(yù)算方案(NOIP2006提高組)主件附件電腦打印機(jī)，掃描儀書(shū)柜圖書(shū)書(shū)桌臺(tái)燈，文具工作椅無(wú)題目描述 Description 金明今天很開(kāi)心，家里購(gòu)置的新房就要領(lǐng)鑰匙了，新房里有一間金明自己專(zhuān)用的很寬敞的房間。更讓他高興的是，媽媽昨天對(duì)他說(shuō)：“你的房間需要購(gòu)買(mǎi)哪些物品，怎么布置，你說(shuō)了算，只要不超過(guò)N元錢(qián)就行”。今天一早，金明就開(kāi)始做預(yù)算了，他把想買(mǎi)的物品分為兩類(lèi)：主件與附件，附件是從屬于某個(gè)主件的，右圖就是一些主件與附件的例子。如果要買(mǎi)歸類(lèi)為

15、附件的物品，必須先買(mǎi)該附件所屬的主件。每個(gè)主件可以有0個(gè)、1個(gè)或2個(gè)附件。附件不再有從屬于自己的附件。金明想買(mǎi)的東西很多，肯定會(huì)超過(guò)媽媽限定的N元。于是，他把每件物品規(guī)定了一個(gè)重要度，分為5等：用整數(shù)15表示，第5等最重要。他還從因特網(wǎng)上查到了每件物品的價(jià)格（都是10元的整數(shù)倍）。他希望在不超過(guò)N元（可以等于N元）的前提下，使每件物品的價(jià)格與重要度的乘積的總和最大。設(shè)第j件物品的價(jià)格為vj，重要度為wj，共選中了k件物品，編號(hào)依次為j1，j2，jk，則所求的總和為：vj1*wj1+vj2*wj2+ +vjk*wjk。（其中*為乘號(hào)）請(qǐng)你幫助金明設(shè)計(jì)一個(gè)滿(mǎn)足要求的購(gòu)物單。34金明的預(yù)算方案(NO

16、IP2006提高組)主件附件電腦打印機(jī)，輸入描述 Input Description 第1行，為兩個(gè)正整數(shù)，用一個(gè)空格隔開(kāi)：N m（其中N（32000）表示總錢(qián)數(shù)，m（60）為希望購(gòu)買(mǎi)物品的個(gè)數(shù)。）從第2行到第m+1行，第j行給出了編號(hào)為j-1的物品的基本數(shù)據(jù)，每行有3個(gè)非負(fù)整數(shù)v p q（其中v表示該物品的價(jià)格（v0，表示該物品為附件，q是所屬主件的編號(hào)）輸出描述 Output Description 只有一個(gè)正整數(shù)，為不超過(guò)總錢(qián)數(shù)的物品的價(jià)格與重要度乘積的總和的最大值(200000)樣例輸入 Sample Input 1000 5800 2 0 400 5 1300 5 1400 3 05

17、00 2 0樣例輸出 Sample Output 2200數(shù)據(jù)范圍及提示 Data Size & Hint 無(wú)35輸入描述 Input Description 35對(duì)于每個(gè)主件，它最多有2個(gè)附件，那么每個(gè)物品只有這幾種情況：1.不帶附件2.帶附件A3.帶附件B4.帶附件A和B5.連主件都不拿那么只要在狀態(tài)轉(zhuǎn)移時(shí)枚舉每個(gè)物品拿還是不拿，拿幾個(gè)附件即可不過(guò)好好看看還是能發(fā)現(xiàn)些什么的：這題放眼望去應(yīng)該是個(gè)樹(shù)形dp，好可怕的說(shuō)36對(duì)于每個(gè)主件，它最多有2個(gè)附件，那么每個(gè)物品只有這幾種情況：至此，背包問(wèn)題全部完成！但這僅僅是簡(jiǎn)單的背包問(wèn)題而已37至此，背包問(wèn)題全部完成！但這僅僅是簡(jiǎn)單的背包問(wèn)題而已37區(qū)

18、間型DP別看我看標(biāo)題38區(qū)間型DP別看我看標(biāo)題38石子歸并經(jīng)典區(qū)間型dp39石子歸并經(jīng)典區(qū)間型dp39題目描述 Description有n堆石子排成一列，每堆石子有一個(gè)重量wi, 每次合并可以合并相鄰的兩堆石子，一次合并的代價(jià)為兩堆石子的重量和wi+wi+1。問(wèn)安排怎樣的合并順序，能夠使得總合并代價(jià)達(dá)到最小。輸入描述 Input Description第一行一個(gè)整數(shù)n（n=100）第二行n個(gè)整數(shù)w1,w2.wn (wi = 100)輸出描述 Output Description一個(gè)整數(shù)表示最小合并代價(jià)樣例輸入 Sample Input44 1 1 4樣例輸出 Sample Output18數(shù)據(jù)

19、范圍及提示 Data Size & Hint無(wú)40題目描述 Description40分析下花費(fèi)吧花費(fèi)是由兩堆石子組成的，即：costij=wi+wi+1+wj-1+wj要合并i-j堆，必須要先合并ik堆和k+1j堆，可以得出遞推式 js(i,j)= wi i=j min( js(i,i) + js(i+1,j) js(i,j-1) + js(j,j) )+costijij41分析下花費(fèi)吧花費(fèi)是由兩堆石子組成的，即：41然后怎么辦？遞歸處理嗎？我說(shuō)你百分百超時(shí)你信嗎？這節(jié)課學(xué)的啥？動(dòng)態(tài)規(guī)劃?。￠_(kāi)個(gè)數(shù)組，記錄下來(lái)，直接轉(zhuǎn)成遞推，時(shí)間復(fù)雜度O(n2)，完全無(wú)壓力P.S.:這個(gè)題寫(xiě)代碼還是稍微有點(diǎn)難

20、度的，所以寫(xiě)不出來(lái)的童鞋可以考慮放(mei)棄(tian)本(yi)題(bian)42然后怎么辦？遞歸處理嗎？我說(shuō)你百分百超時(shí)你信嗎？42能量項(xiàng)鏈(noip2006)題目描述 Description在Mars星球上，每個(gè)Mars人都隨身佩帶著一串能量項(xiàng)鏈。在項(xiàng)鏈上有N顆能量珠。能量珠是一顆有頭標(biāo)記與尾標(biāo)記的珠子，這些標(biāo)記對(duì)應(yīng)著某個(gè)正整數(shù)。并且，對(duì)于相鄰的兩顆珠子，前一顆珠子的尾標(biāo)記一定等于后一顆珠子的頭標(biāo)記。因?yàn)橹挥羞@樣，通過(guò)吸盤(pán)（吸盤(pán)是Mars人吸收能量的一種器官）的作用，這兩顆珠子才能聚合成一顆珠子，同時(shí)釋放出可以被吸盤(pán)吸收的能量。如果前一顆能量珠的頭標(biāo)記為m，尾標(biāo)記為r，后一顆能量珠的頭

21、標(biāo)記為r，尾標(biāo)記為n，則聚合后釋放的能量為m*r*n（Mars單位），新產(chǎn)生的珠子的頭標(biāo)記為m，尾標(biāo)記為n。需要時(shí)，Mars人就用吸盤(pán)夾住相鄰的兩顆珠子，通過(guò)聚合得到能量，直到項(xiàng)鏈上只剩下一顆珠子為止。顯然，不同的聚合順序得到的總能量是不同的，請(qǐng)你設(shè)計(jì)一個(gè)聚合順序，使一串項(xiàng)鏈釋放出的總能量最大。例如：設(shè)N=4，4顆珠子的頭標(biāo)記與尾標(biāo)記依次為(2，3) (3，5) (5，10) (10，2)。我們用記號(hào)表示兩顆珠子的聚合操作，(jk)表示第j，k兩顆珠子聚合后所釋放的能量。則第4、1兩顆珠子聚合后釋放的能量為：(41)=10*2*3=60暫時(shí)找不到能量項(xiàng)鏈這種高級(jí)玩意兒，拿這個(gè)代替下吧43能量項(xiàng)

22、鏈(noip2006)題目描述 Description這一串項(xiàng)鏈可以得到最優(yōu)值的一個(gè)聚合順序所釋放的總能量為(41)2)3）=10*2*3+10*3*5+10*5*10=710輸出描述 Output Description只有一行，是一個(gè)正整數(shù)E（E2.1*109），為一個(gè)最優(yōu)聚合順序所釋放的總能量。樣例輸入 Sample Input42 3 5 10樣例輸出 Sample Output710數(shù)據(jù)范圍及提示 Data Size & Hint無(wú)44這一串項(xiàng)鏈可以得到最優(yōu)值的一個(gè)聚合順序所釋放的總能量為44眾所皆知，絲帶項(xiàng)鏈?zhǔn)黔h(huán)形的，也就是說(shuō)，這個(gè)題相比起石子歸并問(wèn)題來(lái)說(shuō)，變成了環(huán)形擺放，怎么辦呢

23、poi？用腦子想一想，可以想出：即使是一個(gè)環(huán)合并，也不會(huì)合并超過(guò)2圈也就是說(shuō)，可以把這串項(xiàng)鏈看作2倍長(zhǎng)，讀入時(shí)就進(jìn)行預(yù)處理，之后合并時(shí)只要找出在其中一點(diǎn)斷開(kāi)能得到的項(xiàng)鏈的最大能量值就可以了45眾所皆知，絲帶項(xiàng)鏈?zhǔn)黔h(huán)形的，也就是說(shuō)，這個(gè)題相比起石子歸并問(wèn)乘積最大NOIP200046乘積最大NOIP200046題目描述 Description今年是國(guó)際數(shù)學(xué)聯(lián)盟確定的“2000世界數(shù)學(xué)年”，又恰逢我國(guó)著名數(shù)學(xué)家華羅庚先生誕辰90周年。在華羅庚先生的家鄉(xiāng)江蘇金壇，組織了一場(chǎng)別開(kāi)生面的數(shù)學(xué)智力競(jìng)賽的活動(dòng)，你的一個(gè)好朋友XZ也有幸得以參加?；顒?dòng)中，主持人給所有參加活動(dòng)的選手出了這樣一道題目：設(shè)有一個(gè)長(zhǎng)度為

24、N的數(shù)字串，要求選手使用K個(gè)乘號(hào)將它分成K+1個(gè)部分，找出一種分法，使得這K+1個(gè)部分的乘積能夠?yàn)樽畲?。同時(shí)，為了幫助選手能夠正確理解題意，主持人還舉了如下的一個(gè)例子：有一個(gè)數(shù)字串：312， 當(dāng)N=3，K=1時(shí)會(huì)有以下兩種分法：1) 3*12=362) 31*2=62這時(shí)，符合題目要求的結(jié)果是：31*2=62 現(xiàn)在，請(qǐng)你幫助你的好朋友XZ設(shè)計(jì)一個(gè)程序，求得正確的答案。輸入描述 Input Description 程序的輸入共有兩行：第一行共有2個(gè)自然數(shù)N，K（6N40，1K6）第二行是一個(gè)長(zhǎng)度為N的數(shù)字串。47題目描述 Description47輸出描述 Output Description

25、結(jié)果顯示在屏幕上，相對(duì)于輸入，應(yīng)輸出所求得的最大乘積（一個(gè)自然數(shù)）。樣例輸入 Sample Input4 21231樣例輸出 Sample Output62數(shù)據(jù)范圍及提示 Data Size & Hint本題由于比較老，數(shù)據(jù)實(shí)際也比較小，用long long 即可通過(guò)4848這個(gè)題目要求用指定的乘號(hào)數(shù)量分開(kāi)一個(gè)數(shù)，將它變得盡可能大，先找遞推式：aijk=max(aiik-1*ai+1jk-1aij-1k-1*ajjk-1)aijk的含義為：從i到j(luò)段，使用了k個(gè)乘號(hào)所產(chǎn)生的最大乘積，還可以簡(jiǎn)化為aik，含義為從1到i段使用了k個(gè)乘號(hào)所產(chǎn)生的最大乘積記錄到dp數(shù)組里進(jìn)行動(dòng)態(tài)規(guī)劃就好了49這個(gè)題目

26、要求用指定的乘號(hào)數(shù)量分開(kāi)一個(gè)數(shù)，將它變得盡可能大，先數(shù)的劃分(NOIP2001)題目描述 Description將整數(shù)n分成k份，且每份不能為空，任意兩種劃分方案不能相同(不考慮順序)。例如：n=7，k=3，下面三種劃分方案被認(rèn)為是相同的。1 1 51 5 15 1 1問(wèn)有多少種不同的分法。50數(shù)的劃分(NOIP2001)題目描述 Description輸入描述 Input Description輸入：n，k (6n=200，2=k=6)輸出描述 Output Description輸出：一個(gè)整數(shù)，即不同的分法。樣例輸入 Sample Input 7 3樣例輸出 Sample Output4數(shù)

27、據(jù)范圍及提示 Data Size & Hint 四種分法為：1，1，5;1，2，4;1，3，3;2，2，3;51輸入描述 Input Description51這個(gè)題目需要讓人感到獵奇( 不要想歪)的動(dòng)態(tài)規(guī)劃：對(duì)于一個(gè)數(shù)的劃分方式，我們可以分為兩種：1.劃分的結(jié)果中有數(shù)字1的2.劃分的結(jié)果中沒(méi)有數(shù)字1的對(duì)于會(huì)產(chǎn)生數(shù)字1的劃分結(jié)果，我們可以忽略掉那個(gè)1，那么，n劃分成m部分有多少種方法等于n-1劃分成m-1部分有多少種方法，對(duì)于不產(chǎn)生數(shù)字1的劃分結(jié)果，我們有另一種巧妙的辦法：所有劃分產(chǎn)生的數(shù)字統(tǒng)一減1，那么， n劃分成m部分有多少種方法等于n-m劃分成m部分有多少種方法dpij=dpi-1j-1

28、+dpi-jj52這個(gè)題目需要讓人感到獵奇( 不要想歪)的動(dòng)態(tài)規(guī)劃：52總的來(lái)說(shuō)，區(qū)間型dp要比背包型dp難一些，所以下面來(lái)點(diǎn)簡(jiǎn)單的dp53總的來(lái)說(shuō)，區(qū)間型dp要比背包型dp難一些，所以下面來(lái)點(diǎn)簡(jiǎn)單序列型dp傳說(shuō)中最水的dp54序列型dp傳說(shuō)中最水的dp54最長(zhǎng)上升子序列題目描述 Description給一個(gè)數(shù)組a1, a2 . an，找到最長(zhǎng)的上升降子序列ab1ab2 . abk，其中b1b2.bk。輸出長(zhǎng)度即可。輸入描述 Input Description第一行，一個(gè)整數(shù)N。第二行 ，N個(gè)整數(shù)（N = 5000）輸出描述 Output Description輸出K的極大值，即最長(zhǎng)不下降子序

29、列的長(zhǎng)度樣例輸入 Sample Input59 3 6 2 7樣例輸出 Sample Output3數(shù)據(jù)范圍及提示 Data Size & Hint【樣例解釋】最長(zhǎng)不下降子序列為3,6,755最長(zhǎng)上升子序列題目描述 Description樣例輸入 Sa這題還用講么？RT我的做法是開(kāi)一個(gè)dp數(shù)組，記錄下以該數(shù)字為開(kāi)頭且?guī)в性摂?shù)字的最長(zhǎng)上升子序列的長(zhǎng)度，應(yīng)該沒(méi)有和我一樣的56這題還用講么？RT我的做法是開(kāi)一個(gè)dp數(shù)組，記錄下以該數(shù)字為合唱隊(duì)形(NOIP2004)題目描述 Description N位同學(xué)站成一排，音樂(lè)老師要請(qǐng)其中的(N-K)位同學(xué)出列，使得剩下的K位同學(xué)排成合唱隊(duì)形。 合唱隊(duì)形是指

30、這樣的一種隊(duì)形：設(shè)K位同學(xué)從左到右依次編號(hào)為1，2，K，他們的身高分別為T(mén)1，T2，TK， 則他們的身高滿(mǎn)足T1.Ti+1TK(1=i=K)。你的任務(wù)是，已知所有N位同學(xué)的身高，計(jì)算最少需要幾位同學(xué)出列，可以使得剩下的同學(xué)排成合唱隊(duì)形。輸入描述 Input Description輸入文件chorus.in的第一行是一個(gè)整數(shù)N(2=N=100)，表示同學(xué)的總數(shù)。第一行有n個(gè)整數(shù)，用空格分隔，第i個(gè)整數(shù)Ti(130=Ti=230)是第i位同學(xué)的身高(厘米)。輸出描述 Output Description輸出文件chorus.out包括一行，這一行只包含一個(gè)整數(shù)，就是最少需要幾位同學(xué)出列。57合唱隊(duì)

31、形(NOIP2004)題目描述 Description樣例輸入 Sample Input8186 186 150 200 160 130 197 220樣例輸出 Sample Output4數(shù)據(jù)范圍及提示 Data Size & Hint對(duì)于50的數(shù)據(jù)，保證有n=20；對(duì)于全部的數(shù)據(jù)，保證有n=100。58樣例輸入 Sample Input58算法1這道題要求百擺成合唱隊(duì)形，即前面一段單調(diào)遞增，后面一段單調(diào)下降的序列于是就有了算法1：枚舉隊(duì)伍中的最高點(diǎn)，前后的隊(duì)伍分別求最長(zhǎng)上升子序列和最長(zhǎng)下降子序列，時(shí)間復(fù)雜度O(n*2*n2)=O(n3)雖然不超時(shí)，但是敲起代碼來(lái)有點(diǎn)麻煩額59算法1這道題要

32、求百擺成合唱隊(duì)形，即前面一段單調(diào)遞增，后面一算法2：既然要枚舉每一個(gè)點(diǎn)，不如直接求出以每個(gè)點(diǎn)為開(kāi)頭或結(jié)尾的最長(zhǎng)上升和最長(zhǎng)下降子序列，然后直接for一遍找出二者相加的最大值再減去1(因?yàn)殛?duì)伍只有一個(gè)最高點(diǎn))即可代碼簡(jiǎn)化了不少，而且時(shí)間復(fù)雜度壓到了O(n2)！60算法2：既然要枚舉每一個(gè)點(diǎn)，不如直接求出以每個(gè)點(diǎn)為開(kāi)頭或結(jié)尾大家都知道最長(zhǎng)公共子序列和最長(zhǎng)嚴(yán)格上升子序列吧都是大水題吧總有些不好的預(yù)感額61大家都知道最長(zhǎng)公共子序列和最長(zhǎng)嚴(yán)格上升子序列吧都是大水題吧但是如果將兩者結(jié)合起來(lái)呢？那就是LCIS(Longest Common Increasing Subsequence)最長(zhǎng)公共嚴(yán)格上升子序列！

33、果然來(lái)了62但是如果將兩者結(jié)合起來(lái)呢？那就是LCIS(Longest 題目描述 Description熊大媽的奶牛在小沐沐的熏陶下開(kāi)始研究信息題目。小沐沐先讓奶牛研究了最長(zhǎng)上升子序列，再讓他們研究了最長(zhǎng)公共子序列，現(xiàn)在又讓他們要研究最長(zhǎng)公共上升子序列了。小沐沐說(shuō)，對(duì)于兩個(gè)串A，B，如果它們都包含一段位置不一定連續(xù)的數(shù)字，且數(shù)字是嚴(yán)格遞增的，那么稱(chēng)這一段數(shù)字是兩個(gè)串的公共上升子串，而所有的公共上升子串中最長(zhǎng)的就是最長(zhǎng)公共上升子串了。奶牛半懂不懂，小沐沐要你來(lái)告訴奶牛什么是最長(zhǎng)公共上升子串。不過(guò)，只要告訴奶牛它的長(zhǎng)度就可以了。輸入描述 Input Description第一行N，表示A，B的長(zhǎng)度。

34、第二行，串A。第三行，串B。輸出描述 Output Description輸出長(zhǎng)度。63題目描述 Description63樣例輸入 Sample Input42 2 1 32 1 2 3樣例輸出 Sample Output2數(shù)據(jù)范圍及提示 Data Size & Hint1=N=3000，A，B中的數(shù)字不超過(guò)maxlongint64樣例輸入 Sample Input64這題說(shuō)實(shí)話(huà)我也不大會(huì)不過(guò)我還得硬著頭皮講好吧正題開(kāi)始：dpij表示a串前i個(gè)數(shù)和b串前j個(gè)數(shù)且以b串第j個(gè)數(shù)結(jié)尾的最長(zhǎng)公共嚴(yán)格上升子序列(好繞口以后就叫LCIS了)LCIS的長(zhǎng)度，然后根據(jù)最長(zhǎng)公共子序列一題的狀態(tài)轉(zhuǎn)移方程式可以

35、得出本題的狀態(tài)轉(zhuǎn)移方程式： dpij=dpi-1j (ai!=bj) dpij=max(dpi-1k)+1 (ai=bj&akbj)應(yīng)該不是很難懂填充dp數(shù)組不用我教了吧恭喜各位完成序列型dp65這題說(shuō)實(shí)話(huà)我也不大會(huì)不過(guò)我還得硬著頭皮講好吧正題開(kāi)始棋盤(pán)型dp最終boss前的最后一個(gè)dp66棋盤(pán)型dp最終boss前的最后一個(gè)dp66過(guò)河卒A 點(diǎn)有一個(gè)過(guò)河卒，需要走到目標(biāo) B 點(diǎn)。卒行走規(guī)則：可以向下、或者向右。同時(shí)在棋盤(pán)上的任一點(diǎn)有一個(gè)對(duì)方的馬（如上圖的C點(diǎn)），該馬所在的點(diǎn)和所有跳躍一步可達(dá)的點(diǎn)稱(chēng)為對(duì)方馬的控制點(diǎn)。例如上圖 C 點(diǎn)上的馬可以控制 9 個(gè)點(diǎn)（圖中的P1，P2 P8 和 C）。卒不能

36、通過(guò)對(duì)方馬的控制點(diǎn)。棋盤(pán)用坐標(biāo)表示，A 點(diǎn)（0，0）、B 點(diǎn)（n,m）(n,m 為不超過(guò) 20 的整數(shù)，并由鍵盤(pán)輸入)，同樣馬的位置坐標(biāo)是需要給出的（約定: C不等于A，同時(shí)C不等于B）。現(xiàn)在要求你計(jì)算出卒從 A 點(diǎn)能夠到達(dá) B 點(diǎn)的路徑的條數(shù)。1=n,m=15大水題一枚67過(guò)河卒A 點(diǎn)有一個(gè)過(guò)河卒，需要走到目標(biāo) B 點(diǎn)。卒行走規(guī)則：水水就過(guò)了唄卒走到一個(gè)格子的方式只有兩種：1.從它左邊的格子過(guò)來(lái)2.從它上面的格子過(guò)來(lái)那么，走到這個(gè)格子的方法數(shù)=走到上面格子的方法數(shù)+走到左邊格子的方法數(shù)68水水就過(guò)了唄卒走到一個(gè)格子的方式只有兩種：68騎士游歷題目描述 Description 設(shè)有一個(gè)n*m的

37、棋盤(pán)（2n50，2m50），如下圖，在棋盤(pán)上有一個(gè)中國(guó)象棋馬。規(guī)定：1)馬只能走日字2)馬只能向右跳問(wèn)給定起點(diǎn)x1,y1和終點(diǎn)x2,y2，求出馬從x1,y1出發(fā)到x2,y2的合法路徑條數(shù)。 輸入描述 Input Description 第一行2個(gè)整數(shù)n和m第二行4個(gè)整數(shù)x1,y1,x2,y2輸出描述 Output Description 輸出方案數(shù)樣例輸入 Sample Input 30 301 15 3 15樣例輸出 Sample Output 2數(shù)據(jù)范圍及提示 Data Size & Hint 2=n,m=50NOIP199769騎士游歷題目描述 Description NOIP19976

38、和過(guò)河卒有什么區(qū)別額不就是改改狀態(tài)轉(zhuǎn)移方程式啊這個(gè)還不會(huì)的話(huà)還要不要來(lái)Loi啊70和過(guò)河卒有什么區(qū)別額不就是改改狀態(tài)轉(zhuǎn)移方程式啊70傳紙條(NOIP2008)題目描述 Description小淵和小軒是好朋友也是同班同學(xué)，他們?cè)谝黄鹂傆姓劜煌甑脑?huà)題。一次素質(zhì)拓展活動(dòng)中，班上同學(xué)安排做成一個(gè)m行n列的矩陣，而小淵和小軒被安排在矩陣對(duì)角線的兩端，因此，他們就無(wú)法直接交談了。幸運(yùn)的是，他們可以通過(guò)傳紙條來(lái)進(jìn)行交流。紙條要經(jīng)由許多同學(xué)傳到對(duì)方手里，小淵坐在矩陣的左上角，坐標(biāo)(1,1)，小軒坐在矩陣的右下角，坐標(biāo)(m,n)。從小淵傳到小軒的紙條只可以向下或者向右傳遞，從小軒傳給小淵的紙條只可以向上或者向

39、左傳遞。在活動(dòng)進(jìn)行中，小淵希望給小軒傳遞一張紙條，同時(shí)希望小軒給他回復(fù)。班里每個(gè)同學(xué)都可以幫他們傳遞，但只會(huì)幫他們一次，也就是說(shuō)如果此人在小淵遞給小軒紙條的時(shí)候幫忙，那么在小軒遞給小淵的時(shí)候就不會(huì)再幫忙。反之亦然。還有一件事情需要注意，全班每個(gè)同學(xué)愿意幫忙的好感度有高有低（注意：小淵和小軒的好心程度沒(méi)有定義，輸入時(shí)用0表示），可以用一個(gè)0-100的自然數(shù)來(lái)表示，數(shù)越大表示越好心。小淵和小軒希望盡可能找好心程度高的同學(xué)來(lái)幫忙傳紙條，即找到來(lái)回兩條傳遞路徑，使得這兩條路徑上同學(xué)的好心程度只和最大。現(xiàn)在，請(qǐng)你幫助小淵和小軒找到這樣的兩條路徑。輸入描述 Input Description輸入的第一行有

40、2個(gè)用空格隔開(kāi)的整數(shù)m和n，表示班里有m行n列（1=m,n=50）。接下來(lái)的m行是一個(gè)m*n的矩陣，矩陣中第i行j列的整數(shù)表示坐在第i行j列的學(xué)生的好心程度。每行的n個(gè)整數(shù)之間用空格隔開(kāi)。71傳紙條(NOIP2008)題目描述 Description7輸出描述 Output Description輸出共一行，包含一個(gè)整數(shù)，表示來(lái)回兩條路上參與傳遞紙條的學(xué)生的好心程度之和的最大值。樣例輸入 Sample Input3 30 3 92 8 55 7 0樣例輸出 Sample Output34數(shù)據(jù)范圍及提示 Data Size & Hint30%的數(shù)據(jù)滿(mǎn)足：1=m,n=10100%的數(shù)據(jù)滿(mǎn)足：1=m

41、,n=5003928557072輸出描述 Output Description0392855大家有什么想法呢？73大家有什么想法呢？73首先，我們可以輕松的得到一個(gè)錯(cuò)誤的算法：跑兩遍數(shù)字三角形，很明顯這個(gè)算法是錯(cuò)誤的：因?yàn)橛锌赡艹霈F(xiàn)重復(fù)的路徑，那么，這個(gè)算法就沒(méi)用了嗎？當(dāng)然不是的！我們這個(gè)算法的想法是：先找出好心值最高的路徑，然后歸零，找好心值次高的路徑，但是這樣會(huì)導(dǎo)致出現(xiàn)重復(fù)路徑，那么我們稍微改一下這個(gè)算法：讓兩人同時(shí)找好心值最高的路徑那不就亂套了了嗎？！所以，我們要改一下這個(gè)方法：讓兩人同時(shí)從左上角到右下角走，這樣的話(huà)只要兩人不走到同一個(gè)格子上(起點(diǎn)和終點(diǎn)除外)，那么這條路徑就是可行的！d

42、pijkl分別記錄紙條A和紙條B所在的位置，轉(zhuǎn)移時(shí)考慮4種情況：1.A紙條向右，B紙條也向右2.A紙條向右，B紙條向下3.A紙條向下，B紙條也向下4.A紙條向下，B紙條向右74首先，我們可以輕松的得到一個(gè)錯(cuò)誤的算法：跑兩遍數(shù)字三角形，很可是還能再優(yōu)化不是嗎？由于兩張紙條移動(dòng)的格子數(shù)是相同的，所以他們一定在同一條斜線上，所以dp數(shù)組優(yōu)化到三維：i,j,k分別表示走過(guò)的格子數(shù)，紙條A所在的行，紙條B所在的行，這樣，三維數(shù)組就可以表示出狀態(tài)來(lái)，而且還減去了許多無(wú)用的狀態(tài)75可是還能再優(yōu)化不是嗎？由于兩張紙條移動(dòng)的格子數(shù)是相同的，所以最終鬼畜道化師M【】樹(shù)形dp&狀壓DP&DP騙分 (僅簡(jiǎn)單講解)76

43、最終鬼畜道化師M【】樹(shù)形dp&狀樹(shù)形dp顧名思義，在樹(shù)上進(jìn)行的DP鄭州學(xué)習(xí)時(shí)應(yīng)該有講過(guò)由于這一部分的題目我也不太會(huì)，所以每一部分只講一題77樹(shù)形dp顧名思義，在樹(shù)上進(jìn)行的DP77沒(méi)有上司的舞會(huì)題目描述 Description Ural大學(xué)有N個(gè)職員，編號(hào)為1N。他們有從屬關(guān)系，也就是說(shuō)他們的關(guān)系就像一棵以校長(zhǎng)為根的樹(shù)，父結(jié)點(diǎn)就是子結(jié)點(diǎn)的直接上司。每個(gè)職員有一個(gè)快樂(lè)指數(shù)。現(xiàn)在有個(gè)周年慶宴會(huì)，要求與會(huì)職員的快樂(lè)指數(shù)最大。但是，沒(méi)有職員愿和直接上司一起與會(huì)。輸入描述 Input Description第一行一個(gè)整數(shù)N。(1=N=6000)接下來(lái)N行，第i+1行表示i號(hào)職員的快樂(lè)指數(shù)Ri。(-128=

44、Ri=127)接下來(lái)N-1行，每行輸入一對(duì)整數(shù)L,K。表示K是L的直接上司。最后一行輸入0,0。輸出描述 Output Description輸出最大的快樂(lè)指數(shù)。78沒(méi)有上司的舞會(huì)78樣例輸入 Sample Input71 1 1 1 1 1 11 32 36 47 44 53 50 0樣例輸出 Sample Output579樣例輸入 Sample Input79嘛，這也是道很經(jīng)典的樹(shù)形dp題目了這道題的評(píng)級(jí)是Diamond鉆石 ，怎么看也不是noip提高難度的題 不過(guò)我還是得講對(duì)于一個(gè)職員來(lái)說(shuō)，他只有兩種狀態(tài)：參加，不參加；有些人是不是想到狀壓那邊去了看本題數(shù)據(jù)范圍?。?000??！那么，這

45、題是不是就不可解了呢？80嘛，這也是道很經(jīng)典的樹(shù)形dp題目了這道題的評(píng)級(jí)是Diamon當(dāng)然可以解！不然為啥要出這道題對(duì)于一個(gè)職員來(lái)說(shuō)，他要么來(lái)，要么不來(lái)，如果他來(lái)，那么他的下屬就一個(gè)都不敢來(lái)(這是廢話(huà)，如果你的班主任天天去逛銀座，那么你還敢去銀座嗎？)于是，我們可以這樣做：為啥到了關(guān)鍵時(shí)候就翻頁(yè)81當(dāng)然可以解！不然為啥要出這道題81開(kāi)數(shù)組dp60002，dpi0代表i號(hào)職員不來(lái)時(shí)能得到的快樂(lè)值，dpi1則代表i號(hào)職員來(lái)時(shí)能得到的最大快樂(lè)值當(dāng)這個(gè)人不來(lái)時(shí)，對(duì)他的下屬是沒(méi)有影響的，或者說(shuō)，他的下屬愛(ài)來(lái)來(lái)，不愛(ài)來(lái)不來(lái)所以可得：dpi0=max(dpk0,dpk1)，這里的k代表他的所有下屬。因?yàn)樗?/p>

46、來(lái)，他的下屬來(lái)不來(lái)都行，而且對(duì)他的上司又沒(méi)有影響，所以我們可以貪心的找最大的；dpi1=dpk0+ai，k依然代表他的所有下屬。如果他來(lái)了，那么他的下屬就都不能來(lái)，所以就是他的下屬全都不來(lái)的最大快樂(lè)值加上他的快樂(lè)值。這樣就好做了DFS一遍求出所有人的快樂(lè)值，可以證明，最后產(chǎn)生的圖形一定是一棵樹(shù)，所以，只要最后找出這個(gè)公司的超級(jí)大BOSS，并且找出他來(lái)和不來(lái)兩個(gè)狀態(tài)快樂(lè)值最大的那個(gè)，這個(gè)題就AC啦P.S.:簡(jiǎn)直累人82開(kāi)數(shù)組dp60002，dpi0代表i號(hào)職員不狀壓dpTSP問(wèn)題旅行商問(wèn)題，即TSP問(wèn)題（Travelling Salesman Problem）又譯為旅行推銷(xiāo)員問(wèn)題、貨郎擔(dān)問(wèn)題，是

47、數(shù)學(xué)領(lǐng)域中著名問(wèn)題之一。假設(shè)有一個(gè)旅行商人要拜訪n個(gè)城市，他必須選擇所要走的路徑，路徑的限制是每個(gè)城市只能拜訪一次，而且最后要回到原來(lái)出發(fā)的城市。路徑的選擇目標(biāo)是要求得的路徑路程為所有路徑之中的最小值。這個(gè)有點(diǎn)難懂額沒(méi)關(guān)系，codevs上就有這個(gè)題！83狀壓dpTSP問(wèn)題旅行商問(wèn)題，即TSP問(wèn)題（Travel題目描述 Description有一個(gè)送外賣(mài)的，他手上有n份訂單，他要把n份東西，分別送達(dá)n個(gè)不同的客戶(hù)的手上。n個(gè)不同的客戶(hù)分別在1n個(gè)編號(hào)的城市中。送外賣(mài)的從0號(hào)城市出發(fā)，然后n個(gè)城市都要走一次（一個(gè)城市可以走多次），最后還要回到0點(diǎn)（他的單位），請(qǐng)問(wèn)最短時(shí)間是多少?，F(xiàn)在已知任意兩個(gè)城

48、市的直接通路的時(shí)間。輸入描述 Input Description第一行一個(gè)正整數(shù)n （1=n=15）接下來(lái)是一個(gè)（n+1）*(n+1)的矩陣，矩陣中的數(shù)均為不超過(guò)10000的正整數(shù)。矩陣的i行j列表示第i-1號(hào)城市和j-1號(hào)城市之間直接通路的時(shí)間。當(dāng)然城市a到城市b的直接通路時(shí)間和城市b到城市a的直接通路時(shí)間不一定相同，也就是說(shuō)道路都是單向的。輸出描述 Output Description一個(gè)正整數(shù)表示最少花費(fèi)的時(shí)間8484樣例輸入 Sample Input30 1 10 101 0 1 210 1 0 1010 2 10 0樣例輸出 Sample Output8數(shù)據(jù)范圍及提示 Data Size & Hint1=n=1585樣例輸入 Sampl