最佳答案

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