動(dòng)態(tài)規(guī)劃-作業(yè)

1、例2：城市交通 有n個(gè)城市，編號(hào)1n，有些城市之間有路相連，有些則沒(méi)有，有路則當(dāng)然有一個(gè)距離。現(xiàn)在規(guī)定只能從編號(hào)小的城市走到編號(hào)大的城市，問(wèn)你從編號(hào)為1的城市走到編號(hào)為n的城市要花費(fèi)的最短距離是多少？輸入格式： 先輸入一個(gè)n，表示城市數(shù)，n100。 下面的n行，是一個(gè)n*n的鄰接矩陣map1.n,1.n。 mapi,j=0，表示城市i和城市j之間沒(méi)有路相連，否則為兩者之間的距離。輸出格式： 一個(gè)數(shù)，表示從城市1走到城市n的最短距離。 輸入數(shù)據(jù)保證可以從城市1走到城市n。動(dòng)態(tài)規(guī)劃的引入1輸入樣例： 110 5 3 0 0 0 0 0 0 0 05 0 0 1 6 3 0 0 0 0 03 0 0

2、 0 8 0 4 0 0 0 00 1 0 0 0 0 0 5 6 0 00 6 8 0 0 0 0 5 0 0 00 3 0 0 0 0 0 0 0 8 00 0 4 0 0 0 0 0 0 3 00 0 0 5 5 0 0 0 0 0 30 0 0 6 0 0 0 0 0 0 40 0 0 0 0 8 3 0 0 0 30 0 0 0 0 0 0 3 4 3 0動(dòng)態(tài)規(guī)劃的引入2動(dòng)態(tài)規(guī)劃簡(jiǎn)介 攔截導(dǎo)彈（NOIP1999）問(wèn)題描述： 某國(guó)為了防御敵國(guó)的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng)有一個(gè)缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度

3、。某天，雷達(dá)捕捉到敵國(guó)的導(dǎo)彈來(lái)襲，由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。 輸入導(dǎo)彈的枚數(shù)和導(dǎo)彈依次飛來(lái)的高度（雷達(dá)給出的高度數(shù)據(jù)是不大于30000的正整數(shù)，每個(gè)數(shù)據(jù)之間有一個(gè)空格），計(jì)算這套系統(tǒng)最多能攔截多少導(dǎo)彈？如果要攔截所有導(dǎo)彈最少要配備多少套這種導(dǎo)彈攔截系統(tǒng)？樣例輸入： 8 389 207 155 300 299 170 158 65 樣例輸出： 6（最多能攔截的導(dǎo)彈數(shù)） 2（要攔截所有導(dǎo)彈最少要配備的系統(tǒng)數(shù)）3例3、數(shù)塔問(wèn)題問(wèn)題描述設(shè)有一個(gè)三角形的數(shù)塔，頂點(diǎn)為根結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)有一個(gè)整數(shù)值。從頂點(diǎn)出發(fā)，可以向左走或向右走，如圖所示： 要求從根結(jié)點(diǎn)開(kāi)始，請(qǐng)

4、找出一條路徑，使路徑之和最大，只要輸出路徑的和。輸入數(shù)據(jù)：第一行為n(n100)，表示數(shù)塔的層數(shù)從第2行至n+1行，每行有若干個(gè)數(shù)據(jù)，表示數(shù)塔中的數(shù)值。輸出數(shù)據(jù)：輸出路徑和最大的路徑值。 4例4：跳馬問(wèn)題問(wèn)題描述：馬的路徑問(wèn)題，在一個(gè)n*m的棋盤(pán)上的P點(diǎn)有一個(gè)中國(guó)象棋的馬，而另一個(gè)點(diǎn)Q為馬的家，同時(shí)約定，Q在P的右邊，如下圖所示：試找出從P到Q的所有通路的條數(shù)。PQ窮舉算法遞歸算法52007_2(普及組)（最短路線(xiàn)）某城市的街道是一個(gè)很規(guī)整的矩形網(wǎng)格（見(jiàn)下圖），有7 條南北向的縱街，5 條東西向的橫街?，F(xiàn)要從西南角的A 走到東北角的B，最短的走法共有多少種？_. AB6 AB A點(diǎn)到B點(diǎn)的路徑數(shù)量7例5：思考：求最長(zhǎng)不下降序列問(wèn)題描述：設(shè)有一個(gè)正整數(shù)的序列：b1,b2,bn，對(duì)于下標(biāo)i1i2in，若有bi1bi2 bin，則稱(chēng)存在一個(gè)長(zhǎng)度為l的不下降序列。如下列數(shù)列：13791638243718441921226315存在長(zhǎng)度為5的不下降序列：1316384463存在長(zhǎng)度8的不下降序列：7916181921226