最佳答案

石子合并 在一個(gè)圓形操場(chǎng)的四周擺放著N堆石子(N<= 100),現(xiàn)要將石子有次序地合并成一堆.規(guī)定每次只能選取相鄰的兩堆合并成新的一堆,并將新的一堆的石子數(shù),記為該次合并的得分.編一程序,由文件讀入堆棧數(shù)N及每堆棧的石子數(shù)(<=20). (!)選擇一種合并石子的方案,使用權(quán)得做N-1次合并,得分的總和最小; (2)選擇一種合并石子的方案,使用權(quán)得做N-1次合并,得分的總和最小; 輸入數(shù)據(jù): 第一行為石子堆數(shù)N; 第二行為每堆的石子數(shù),每?jī)蓚�(gè)數(shù)之間用一個(gè)空格分隔. 輸出數(shù)據(jù): 從第一至第N行為得分最小的合并方案.第N+1行是空行.從第N+2行到第2N+1行是得分最大合并方案.每種合并方案用N行表示,其中第i行(1<=i<=N)表示第i次合并前各堆的石子數(shù)(依順時(shí)針次序輸出,哪一堆先輸出均可).要求將待合并的兩堆石子數(shù)以相應(yīng)的負(fù)數(shù)表示. 輸入輸出范例: 輸入: 4 4 5 9 4 輸出: -4 5 9 -4 -8 -5 9 -13 -9 22 4 -5 -9 4 4 -14 -4 -4 -18 22 最小代價(jià)子母樹 設(shè)有一排數(shù)，共n個(gè)，例如:22 14 7 13 26 15 11.任意2個(gè)相鄰的數(shù)可以進(jìn)行歸并,歸并的代價(jià)為該兩個(gè)數(shù)的和,經(jīng)過不斷的歸并,最后歸為一堆,而全部歸并代價(jià)的和稱為總代價(jià),給出一種歸并算法,使總代價(jià)為最小. 輸入、輸出數(shù)據(jù)格式與“石子合并”相同。 輸入樣例: 4 12 5 16 4 輸出樣例: -12 -5 16 4 17 -16 -4 -17 -20 37 背包問題 設(shè)有n種物品，每種物品有一個(gè)重量及一個(gè)價(jià)值。但每種物品的數(shù)量是無限的，同時(shí)有一個(gè)背包，最大載重量為XK，今從n種物品中選取若干件(同一種物品可以多次選取)，使其重量的和小于等于XK，而價(jià)值的和為最大。 輸入數(shù)據(jù): 第一行兩個(gè)數(shù):物品總數(shù)N，背包載重量XK;兩個(gè)數(shù)用空格分隔; 第二行N個(gè)數(shù),為N種物品重量;兩個(gè)數(shù)用空格分隔; 第三行N個(gè)數(shù),為N種物品價(jià)值; 兩個(gè)數(shù)用空格分隔; 輸出數(shù)據(jù): 第一行總價(jià)值; 以下N行，每行兩個(gè)數(shù)，分別為選取物品的編號(hào)及數(shù)量; 輸入樣例: 4 10 2 3 4 7 1 3 5 9 輸出樣例: 12 2 1 4 1 商店購(gòu)物 某商店中每種商品都有一個(gè)價(jià)格。例如，一朵花的價(jià)格是2 ICU(ICU 是信息學(xué)競(jìng)賽的貨幣的單位);一個(gè)花瓶的價(jià)格是5 ICU。為了吸引更多的顧客，商店提供了特殊優(yōu)惠價(jià)。特殊優(yōu)惠商品是把一種或幾種商品分成一組。并降價(jià)銷售。例如:3朵花的價(jià)格不是6而是5 ICU ;2個(gè)花瓶加1朵花是10 ICU不是12 ICU。 編一個(gè)程序，計(jì)算某個(gè)顧客所購(gòu)商品應(yīng)付的費(fèi)用。 要充分利用優(yōu)惠價(jià)以使顧客付款最小。請(qǐng)注意，你不能變更顧客所購(gòu)商品的種類及數(shù)量， 即使增加某些商品會(huì)使付款總數(shù)減小也不允許你作出任何變更。假定各種商品價(jià)格用優(yōu)惠價(jià)如上所述， 并且某顧客購(gòu)買物品為:3朵花和2個(gè)花瓶。那么顧客應(yīng)付款為14 ICU因?yàn)? 1朵花加2個(gè)花瓶: 優(yōu)惠價(jià):10 ICU 2朵花 正常價(jià): 4 ICU 輸入數(shù)據(jù) 用兩個(gè)文件表示輸入數(shù)據(jù)。第一個(gè)文件INPUT.TXT描述顧客所購(gòu)物品(放在購(gòu)物筐中);第二個(gè)文件描述商店提供的優(yōu)惠商品及價(jià)格(文件名為OFF ER.TXT)。 兩個(gè)文件中都只用整數(shù)。 第一個(gè)文件INPUT.TXT的格式為:第一行是一個(gè)數(shù)字B(0≤B≤5)，表示所購(gòu)商品種類數(shù)。下面共B行，每行中含3個(gè)數(shù)C，K，P。 C 代表商品的編碼(每種商品有一個(gè)唯一的編碼)，1≤C≤999。K代表該種商品購(gòu)買總數(shù)，1≤K≤5。P 是該種商品的正常單價(jià)(每件商品的價(jià)格)，1≤P≤999。請(qǐng)注意，購(gòu)物筐中最多可放5*5=25件商品。 第二個(gè)文件OFFER.TXT的格式為:第一行是一個(gè)數(shù)字S(0≤S≤9 9)，表示共有S 種優(yōu)惠。下面共S行，每一行描述一種優(yōu)惠商品的組合中商品的種類。下面接著是幾個(gè)數(shù)字對(duì)(C，K)，其中C代表商品編碼，1≤C≤9 99。K代表該種商品在此組合中的數(shù)量，1≤K≤5。本行最后一個(gè)數(shù)字P(1≤ P≤9999)代表此商品組合的優(yōu)惠價(jià)。當(dāng)然， 優(yōu)惠價(jià)要低于該組合中商品正常價(jià)之總和。 輸出數(shù)據(jù) 在輸出文件OUTPUT.TXT中寫 一個(gè)數(shù)字(占一行)， 該數(shù)字表示顧客所購(gòu)商品(輸入文件指明所購(gòu)商品)應(yīng)付的最低貨款。 輸入/輸出數(shù)據(jù)舉例 ┌--------┐ ┌------------┐┌--------┐ │ INPUT │ │ OFFER.TXT ││ OUTPUT.TXT│ ├--------┤ ├------------┤├--------┤ │ 2 │ │ 2 ││ 14 │ │ 7 3 2 │ │ 1 7 3 5 ││ │ │ 8 2 5 │ │ 2 7 1 8 2 10 ││ │ └--------┘ └------------┘└--------┘ 簡(jiǎn)析: 算法: 動(dòng)態(tài)規(guī)劃 數(shù)據(jù)結(jié)構(gòu): 字符串 題型: II 型 難度: 4 分 編程時(shí)間: 4分鐘 簡(jiǎn)述: 本題競(jìng)賽時(shí)有一個(gè)很長(zhǎng)的文件測(cè)試數(shù)據(jù)，用動(dòng)態(tài)規(guī)劃可較快的出答 案。 旅游預(yù)算 一個(gè)旅行社需要估算乘汽車從某城市到另一城市的最小費(fèi)用，沿路有若干加油站，每個(gè)加油站收費(fèi)不一定相同。 旅游預(yù)算有如下規(guī)則: 若油箱的油過半，不停車加油，除非油箱中的油不可支持到下一站;每次加油時(shí)都加滿;在一個(gè)加油站加油時(shí)，司機(jī)要花費(fèi)2元買東西吃;司機(jī)不必為其他意外情況而準(zhǔn)備額外的油;汽車開出時(shí)在起點(diǎn)加滿油箱;計(jì)算精確到分(1元=100分)。編寫程序估計(jì)實(shí)際行駛在某路線所需的最小費(fèi)用。 輸入格式: 從當(dāng)前目錄下的文本文件“route.dat”讀入數(shù)據(jù)。按以下格式輸入若干旅行路線的情況: 第一行為起點(diǎn)到終點(diǎn)的距離(實(shí)數(shù)) 第二行為三個(gè)實(shí)數(shù)，后跟一個(gè)整數(shù)，每?jī)蓚�(gè)數(shù)據(jù)間用一個(gè)空格隔開。其中第一個(gè)數(shù)為汽車油箱的容量(升)，第二個(gè)數(shù)是每升汽油行駛的公里數(shù)，第三個(gè)數(shù)是在起點(diǎn)加滿油箱的費(fèi)用，第四個(gè)數(shù)是加油站的數(shù)量。(〈=50)。接下去的每行包括兩個(gè)實(shí)數(shù)，每個(gè)數(shù)據(jù)之間用一個(gè)空格分隔，其中第一個(gè)數(shù)是該加油站離起點(diǎn)的距離，第二個(gè)數(shù)是該加油站每升汽油的價(jià)格(元/升)。加油站按它們與起點(diǎn)的距離升序排列。所有的輸入都有一定有解。 輸出格式: 答案輸出到當(dāng)前目錄下的文本文件“route.out”中。 該文件包括兩行。第一行為一個(gè)實(shí)數(shù)和一個(gè)整數(shù)，實(shí)數(shù)為旅行的最小費(fèi)用，以元為單位，精確到分，整數(shù)表示途中加油的站的N。第二行是N個(gè)整數(shù)，表示N個(gè)加油的站的編號(hào)，按升序排列。數(shù)據(jù)間用一個(gè)空格分隔，此外沒有多余的空格。 輸入輸出舉例: 輸入文件:(route.dat) 輸出文件(route.out) 516.3 38.09 1 15.7 22.1 20.87 3 2 125.4 1.259 297.9 1.129 345.2 0.999 海上交通控制 海上交通圖可以用一個(gè)有向圖來表示，頂點(diǎn)表示港口，邊表示兩個(gè)港口之間是否有航線可通。為保證海上交通安全和以盡量快的速度到達(dá)目的地，每艘船在出發(fā)前都將航行計(jì)劃(包括出發(fā)時(shí)間、速度、出發(fā)與到達(dá)港口)提交給海上交通控制局，由海上交通控制局為它們制定航線�，F(xiàn)給出一系列的船只航行計(jì)劃(包括出發(fā)時(shí)間、速度、出發(fā)與到達(dá)港口)，請(qǐng)你根據(jù)以下原則編程為它們制定航線: 1、 每艘船在出發(fā)的一瞬間提交航行計(jì)劃(提交和出發(fā)的時(shí)間差可以忽略); 2、 每艘船都嚴(yán)格按照出發(fā)時(shí)間出發(fā)，不能提前，也不能延遲; 3、 在任何時(shí)間一條航道(兩港口間的直達(dá)航線)上只能有一艘船，因此，一艘船在出發(fā)的瞬間發(fā)現(xiàn)某航道將在末來的某段時(shí)間內(nèi)會(huì)被在它之前出發(fā)的船占用，則它在那一段時(shí)間內(nèi)將不會(huì)使用該航道，當(dāng)然其余時(shí)間還是可以使用該航道; 4、 每個(gè)港口均可被無限艘船同時(shí)使用; 5、 在滿足上述條件后，要使本船航行的時(shí)間最短; 6、 假如某船不能到達(dá)目標(biāo)港口，那么它將放棄這個(gè)航程; 7、 船在任何時(shí)候都不能停下來，即從出發(fā)后，要一直航行到目的地，中途不得在航道或港口中停留。 時(shí)間用4位數(shù)字表示如2345表示23:45，速度單位用節(jié)(海里/小時(shí))表示。在計(jì)算時(shí)間時(shí)，中間結(jié)果應(yīng)是精確的時(shí)間(即不要四舍五入到分鐘)，而航行時(shí)間的計(jì)算是以總距離除以速度為準(zhǔn)，最終到目標(biāo)地的時(shí)刻應(yīng)是航行時(shí)刻加上航行時(shí)間的四舍五入到分鐘的結(jié)果。 輸入格式: 從當(dāng)前目錄下的文本文件“LANE.DAT”讀入數(shù)據(jù)。輸入的數(shù)據(jù)一定有解，且不會(huì)出現(xiàn)跨越00:00的情況，例如，一艘船在23:55出發(fā)，第二天0:15到達(dá)的情況是不會(huì)出現(xiàn)的。輸入文件開頭是港口定義: 第一行是港口數(shù)N(〈=26); 第二行是一個(gè)長(zhǎng)度為N的大寫字母串，每個(gè)字母表示一個(gè)港口名字; 第三行開始N行的N X N矩陣是一個(gè)鄰接矩陣，每行有N個(gè)整數(shù)，其值為港口間距離(單位為海里)，整數(shù)間以空格分隔(若為0表示兩港口沒有直達(dá)航線相連); 接著的一行是一個(gè)整數(shù)M(〈=50)，表示共有M艘船提交航行計(jì)劃; 接下去的每3行表示一艘船的航行計(jì)劃，其中第一行是船名，第二行是出發(fā)時(shí)間和航速，兩者均為整數(shù)，以一個(gè)空格分隔，第三行是兩個(gè)大寫安母，之間沒有任何分隔，第一個(gè)表示出發(fā)的港口，第二個(gè)表示目的港口; 輸出格式: 答案輸出到當(dāng)前目錄下的文本文件“LANE.OUT”中。該文件的每3行表示一艘船的航線，其中第一行是船名，第二行是出發(fā)時(shí)間和到達(dá)時(shí)間，兩者均為整數(shù)，以一個(gè)空格分隔，第三行是數(shù)個(gè)大寫字母，之間沒有任何分隔，表示該船經(jīng)過的港口(包括出發(fā)和目的港口)。如果這艘船放棄航程時(shí)，到達(dá)時(shí)間用-1來表示，并留空第三行。 注意:在輸入和輸出中航行計(jì)劃和航線均按出發(fā)時(shí)間排序，時(shí)間精確到分鐘。 輸入輸出舉例: 輸入文件:LANE.DAT 輸出文件:LANE.OUT 5 Bluesky ABCDE 800 1000 0 10 0 50 10 CB 10 0 20 70 0 Blackhorse 0 20 0 20 0 900 1100 50 70 20 0 10 AB 10 0 0 10 0 Greenforest 4 1000 1130 Bluesky DEAB 0800 10 Silverboat CB 1200 1300 Blackhorse DC 0900 5 AB Greenforest 1000 20 DB Silverboat 1200 20 DC 防衛(wèi)導(dǎo)彈 一種新型的防衛(wèi)導(dǎo)彈可截?fù)舳鄠�(gè)攻擊導(dǎo)彈。它可以向前飛行，也可以用很快的速度向下飛行，可以毫無損傷地截?fù)暨M(jìn)攻導(dǎo)彈，但不可以向后或向上飛行。但有一個(gè)缺點(diǎn)，盡管它發(fā)射時(shí)可以達(dá)到任意高度，但它只能截?fù)舯人�上次截�(fù)魧?dǎo)彈時(shí)所處高度低或者高度相同的導(dǎo)彈�，F(xiàn)對(duì)這種新型 防衛(wèi)導(dǎo)彈進(jìn)行測(cè)試，在每一次測(cè)試中，發(fā)射一系列的測(cè)試導(dǎo)彈(這些導(dǎo)彈發(fā)射的間隔時(shí)間固定，飛行速度相同)，該防衛(wèi)導(dǎo)彈所能獲得的信息包括各進(jìn)攻導(dǎo)彈的高度，以及它們發(fā)射次序�，F(xiàn)要求編一程序，求在每次測(cè)試中，該防衛(wèi)導(dǎo)彈最多能截?fù)舻倪M(jìn)攻導(dǎo)彈數(shù)量，一個(gè)導(dǎo)彈能被截?fù)魬?yīng)滿足下列兩個(gè)條件之一: 1、 它是該次測(cè)試中第一個(gè)被防衛(wèi)導(dǎo)彈截?fù)舻膶?dǎo)彈; 2、 它是在上一次被截?fù)魧?dǎo)彈的發(fā)射后發(fā)射，且高度不大于上一次被截?fù)魧?dǎo)彈的高度的導(dǎo)彈。 輸入格式: 從當(dāng)前目錄下的文本文件“CATCHER.DAT”讀入數(shù)據(jù)。該文件的第一行是一個(gè)整數(shù)N(0〈=N〈=4000)，表示本次測(cè)試中，發(fā)射的進(jìn)攻導(dǎo)彈數(shù)，以下N行每行各有一個(gè)整數(shù)hi(0〈=hi〈=32767)，表示第i個(gè)進(jìn)攻導(dǎo)彈的高度。文件中各行的行首、行末無多余空格，輸入文件中給出的導(dǎo)彈是按發(fā)射順序排列的。 輸出格式: 答案輸出到當(dāng)前目錄下的文本文件“CATCHER.OUT”中，該文件第一行是一個(gè)整數(shù)max，表示最多能截?fù)舻倪M(jìn)攻導(dǎo)彈數(shù)，以下的max行每行各有一個(gè)整數(shù)，表示各個(gè)被截?fù)舻倪M(jìn)攻導(dǎo)彈的編號(hào)(按被截?fù)舻南群箜樞蚺帕?。輸出的答案可能不唯一，只要輸出其中任一解即可。 輸入輸出舉例: 輸入文件:CATCHER.DAT 輸出文件:CATCHER.OUT 3 2 25 1 36 3 23 求函數(shù)最大值 已知3個(gè)函數(shù)A，B，C值如下表示，自變量取值為0----10的整數(shù)。請(qǐng)用動(dòng)態(tài)規(guī)劃的方法求出一組x，y，z，使得A(x)+B(y)+C(z)為最大，并且滿足x2+y2+z2X 0 1 2 3 4 5 6 7 8 9 10 A(x) 2 4 7 11 13 15 18 22 18 15 11 B(x) 5 10 15 20 24 18 12 9 5 3 1 C(x) 8 12 17 22 19 16 14 11 9 7 4

回答者：yhpuk6282016-01-21 00:00