任務:請寫乙個程式:
在文字檔案tan.in中讀入路程的總長度、旅館的數目和對旅館的描述;
找出兩個旅行的方案:
乙個最便宜的方案(就是付出的宿費最少的方案);如果有多個方案,選擇在旅館中度夜的次數最少的方案;
乙個最短的方案(就是在旅館中度夜的次數最少的方案);如果有多個方案,選擇花費最少的方案;
把結果,就是兩個旅行方案,最便宜和最短的旅行方案,輸出到檔案tan.out中。
【輸入檔案】
在文字檔案tan.in的第一行包括兩個用空格分開的正整數。第乙個整數d為從起點到終點的距離,第二個整數h為旅館的數目,d 16000,h 1000。
以下的h行每行兩個整數,為對旅館的描述。每行中的第乙個整數為旅館距離起點的距離,第二個為旅館的住宿費用,為不大於1000的整數。資料是按照據起點距離遞增的順序排列的。
【輸出檔案】
你應該在文字檔案tan.out中輸出最便宜的旅程方案。也就是說,從起點開始需要過夜的旅館距離起點的距離。
類似的,你應該在檔案的第二行輸出最短的旅程方案。
所有的整數應該的用空格分開。
樣例:輸入(tan.in):
2000 7
100 54
120 70
400 17
700 38
1000 25
1200 18
1440 40
輸出(tan.out):
400 1200
400 1200
3. 蛙人
(ple.pas/c/cpp)
【問題描述】
乙個蛙人現在擁有一些潛水用的特殊器材。這些器材均為一些圓筒,每乙個圓筒中都包含兩個部分,一部分裝氧氣,另一部分裝氮氣。現在我們給出每個圓筒的氮氣和氧氣的含量,還有它們的重量,試根據蛙人所需的兩種氣體的數量計算出蛙人所需攜帶的最少的重量。
示例:假設這個蛙人擁有如下5個圓筒,每乙個圓筒中氧氣、氮氣的含量(公升)和它的重量都用一行三個整數來表示如下:
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119
如果該蛙人需要5公升的氧氣和60公升的氮氣,那麼它至少需要帶2個總重249的圓筒(例如它取第乙個和第二個圓筒或第四個和第五個圓筒)。
任務:請寫乙個程式:
● 從文字檔案ple.in中讀入圓筒的數目和每個圓筒中氧氣、氮氣的含量及它的重量;
● 計算為了滿足蛙人的需要他所需攜帶的最少重量;
● 把結果輸出到文字檔案ple.out中。
注釋:我們給出的資料總是保證可以滿足蛙人的需要的。
【輸入檔案】
在文字檔案ple.in的第一行包括用空格分開的兩個整數t和a,1 ≤ t ≤ 21且1 ≤ a ≤ 79,表示蛙人所需的氧氣和氮氣的體積。第二行包括乙個整數n,1 ≤ n ≤ 1000,為不同圓筒的數目。
以下的n行每行包括乙個對圓筒的描述,第i+2行包括三個用空格分開的整數ti、ai、wi,分別表示第i個圓筒中氧氣、氮氣的含量和該圓筒的重量。
【輸出檔案】
你的程式應該在文字檔案ple.out中輸出唯一的乙個整數,表示為了滿足蛙人的要求,它所需攜帶的最少重量。
樣例:輸入(ple.in):
5 60
53 36 120
10 25 129
5 50 250
1 45 130
4 20 119
輸出(ple.out):
2494.階梯教室裝置利用
代號:rez
我們現有許多演講要在階梯教室中舉行。每乙個演講都可以用唯一的起始和終止時間來確定,如果兩個演講時間有部分或全部重複,那麼它們是無法同時在階級教室中舉行的。現在我們想要盡最大可能的利用這個教室,也就是說,我們需要在這些演講中選擇一些不重複的演講來舉行使得他們用的總時間盡可能的長。
我們假設在某一演講結束的瞬間我們就可以立即開始另乙個演講。
任務:請寫乙個程式:
● 在文字檔案rez.in中讀入所有演講的起始和終止時間;
● 計算最大的可能演講總時間;
● 把結果輸出到文字檔案rez.out中。
輸入格式:
在文字檔案rez.in的第一行包括乙個正整數n,n 10000,為所有的演講的數目。
以下的n行每行含有兩個由空格隔開整數p和k,0 p < k 30000。這樣的一對整數表示乙個演講由時間p開始到時間k結束。
輸出格式:
你應該在文字檔案rez.out輸出唯一的乙個整數,為最長的演講總時間。
樣例:輸入(rez.in):
121 2
3 50 4
6 87 13
4 69 10
9 12
11 14
15 19
14 16
18 20
輸出(rez.out):
165. 順序對齊
源程式名 align.??? (pas,c,cpp)
可執行檔名 align.exe
輸入檔名 align.in
輸出檔名 align.out
考慮兩個字串右對齊的最佳解法。例如,有乙個右對齊方案中字串是aaddefgghc和adcdegh。
aad_defgghc
adcde__gh_
每乙個數值匹配的位置值2分,一段連續的空格值-1分。所以總分是匹配點的2倍減去連續空格的段數,在上述給定的例子中,6個位置(a,d,d,e,g,h)匹配,三段空格,所以得分2*6+(-1)*3=9,注意,我們並不處罰左邊的不匹配位置。若匹配的位置是兩個不同的字元,則既不得分也不失分。
請你寫個程式找出最佳右對齊方案。
輸入輸入檔案包含兩行,每行乙個字串,最長50個字元。字元全部是大字字母。
輸出一行,為最佳對齊的得分。
樣例align.in
aaddefgghc
adcdegh
align.out
96、數字遊戲(game.pas)
【問題描述】丁丁最近沉迷於乙個數字遊戲之中。這個遊戲看似簡單,但丁丁在研究了許多天之後卻發覺原來在簡單的規則下想要贏得這個遊戲並不那麼容易。遊戲是這樣的,在你面前有一圈整數(一共n個),你要按順序將其分為m個部分,各部分內的數字相加,相加所得的m個結果對10取模後再相乘,最終得到乙個數k。
遊戲的要求是使你所得的k最大或者最小。
例如,對於下面這圈數字(n=4,m=2):
當要求最小值時,((2-1) mod 10)×((4+3) mod 10)=1×7=7,要求最大值時,為((2+4+3) mod 10)×(-1 mod 10)=9×9=81。特別值得注意的是,無論是負數還是正數,對10取模的結果均為非負值。
丁丁請你編寫程式幫他贏得這個遊戲。
【輸入格式】輸入檔案第一行有兩個整數,n(1≤n≤50)和m(1≤m≤9)。以下n行每行有個整數,其絕對值不大於104,按順序給出圈中的數字,首尾相接。
【輸出格式】輸出檔案有兩行,各包含乙個非負整數。第一行是你程式得到的最小值,第二行是最大值。
【輸入樣例】
4 243-1
2【輸出樣例】781
設f(i,j)是前j個數分成i部分,所得的最大值
f(i,j)=max
i 普及組不作要求 書的複製 源程式名 book.pas,c,cpp 可執行檔名 輸入檔名 輸出檔名 問題描述 現在要把m本有順序的書分給k個人複製 抄寫 每乙個人的抄寫速度都一樣,一本書不允許給兩個 或以上 的人抄寫,分給每乙個人的書,必須是連續的,比如不能把第 一 第三 第四本數給同乙個人抄寫。現在... 題1 多公尺諾骨牌 domino 問題描述 有一種多公尺諾骨牌是平面的,其正面被分成上下兩部分,每一部分的表面或者為空,或者被標上1至6個點。現有一行排列在桌面上 頂行骨牌的點數之和為6 1 1 1 9 底行骨牌點數之和為1 5 3 2 11。頂行和底行的差值是2。這個差值是兩行點數之和的差的絕對值... 第四章動態規劃 第一節動態規劃原理 一 基本概念 1 引例 例4 1 最短路程問題。某地區需要由發電廠至使用者端架設一條高壓輸電線路,途中經過三個城鎮 每個城鎮又各需建設乙個變電站。城鎮和各有二個站址可供選擇,城鎮有三個站址可供選擇,相互間地理位置如圖4 1所示,圖中各線段旁資料表示該段路徑相對長度...動態規劃部分練習 2
動態規劃練習題及解答
動態規劃講稿