（普及組不作要求）
書的複製
（源程式名 book.???（pas,c,cpp）
可執行檔名
輸入檔名
輸出檔名
[問題描述]：
現在要把m本有順序的書分給k個人複製（抄寫），每乙個人的抄寫速度都一樣，一本書不允許給兩個（或以上）的人抄寫，分給每乙個人的書，必須是連續的，比如不能把第
一、第三、第四本數給同乙個人抄寫。現在請你設計一種方案，使得複製時間最短。複製時間為抄寫頁數最多的人用去的時間。
[輸入格式]：
第一行兩個整數m、k（k<=m<=100）；
第二行m個整數，第i個整數表示第i本書的頁數。
[輸出格式]：
共k行，每行兩個正整數，第i行表示第i個人抄寫的書的起始編號和終止編號。k行的起始編號應該從小到大排列，如果有多解，則盡可能讓前面的人少抄寫。
[樣例輸入]：
9 31 2 3 4 5 6 7 8 9
[樣例輸出]：
1 56 7
8 9最小乘車費用
（源程式名 busses.???（pas,c,cpp）
可執行檔名
輸入檔名
輸出檔名
[問題描述]：
某條街上每一公里就有一汽車站，乘車費用如下表：
而一輛汽車從不行駛超過10公里。某人想行駛n公里，假設他可以任意次換車，請你幫他找到一種乘車方案使費用最小（10公里的費用比1公里小的情況是允許的）。
編一程式：
從檔案中讀入對乘車費用的描述；
算出最小的**；
把結果寫入檔案中。
[輸入格式]：
輸入檔案共兩行，第一行為10個不超過100的整數，依次表示行駛1～10公里的費用，相鄰兩數間用空格隔開；第二行為某人想要行駛的公里數。
[輸出格式]：
輸出檔案僅一行包含乙個整數，表示該測試點的最小費用。
[樣例輸入]：
12 21 31 40 49 58 69 79 90 101
15[樣例輸出]：
147筷子
（源程式名 chop.???（pas,c,cpp）
可執行檔名
輸入檔名
輸出檔名
[問題描述]：
a先生有很多雙筷子。確切的說應該是很多根，因為筷子的長度不一，很難判斷出哪兩根是一雙的。這天，a先生家裡來了k個客人，a先生留下他們吃晚飯。
加上a先生，a夫人和他們的孩子小a，共k+3個人。每人需要用一雙筷子。a先生只好清理了一下筷子，共n根，長度為t1，t2，t3，……，tn。
現在他想用這些筷子組合成k+3雙，使每雙的筷子長度差的平方和最小。（怎麼不是和最小？？這要去問a先生了，呵呵）
[輸入格式]：
輸入檔案共有兩行，第一行為兩個用空格隔開的整數，表示n，k（1≤n≤100，0[輸出格式]：
輸出檔案僅一行。如果湊不齊k+3雙，輸出-1，否則輸出長度差平方和的最小值。
[樣例輸入]：
10 1
1 1 2 3 3 3 4 6 10 20
[樣例輸出]：
5[說明]：
第一雙 1 1
第二雙 2 3
第三雙 3 3
第四雙 4 6
(1-1)^2+(2-3)^2+(3-3)^2+(4-6)^2=5
護衛隊（
源程式名 convoy.???（pas,c,cpp）
可執行檔名
輸入檔名
輸出檔名
[問題描述]：
護衛車隊在一條單行的街道前排成一隊，前面河上是一座單行的橋。因為街道是一條單行道，所以任何車輛都不能超車。橋能承受乙個給定的最大承載量。
為了控制橋上的交通，橋兩邊各站乙個指揮員。護衛車隊被分成幾個組，每組中的車輛都能同時通過該橋。當一組車隊到達了橋的另一端，該端的指揮員就用**通知另一端的指揮員，這樣下一組車隊才能開始通過該橋。
每輛車的重量是已知的。任何一組車隊的重量之和不能超過橋的最大承重量。被分在同一組的每一輛車都以其最快的速度通過該橋。
一組車隊通過該橋的時間是用該車隊中速度最慢的車通過該橋所需的時間來表示的。問題要求計算出全部護衛車隊通過該橋所需的最短時間值。
[輸入格式]：
輸入檔案第一行包含三個正整數（用空格隔開），第乙個整數表示該橋所能承受的最大載重量（用噸表示）；第二個整數表示該橋的長度（用千公尺表示）；第三個整數表示該護衛隊中車輛的總數（n<1000）。接下來的幾行中，每行包含兩個正整數w和s（用空格隔開），w表示該車的重量（用噸表示），s表示該車過橋能達到的最快速度（用千公尺/小時表示）。車子的重量和速度是按車子排隊等候時的順序給出的。
[輸出格式]：
輸出檔案應該是乙個實數，四捨五入精確到小數點後1位，表示整個護衛車隊通過該橋所需的最短時間（用分鐘表示）。
[樣例輸入]：
100 5 10
40 25
50 20
50 20
70 10
12 50
9 70
49 30
38 25
27 50
19 70
[樣例輸出]：
75.0
動態規劃練習
任務 請寫乙個程式 在文字檔案tan.in中讀入路程的總長度 旅館的數目和對旅館的描述 找出兩個旅行的方案 乙個最便宜的方案 就是付出的宿費最少的方案 如果有多個方案，選擇在旅館中度夜的次數最少的方案 乙個最短的方案 就是在旅館中度夜的次數最少的方案 如果有多個方案，選擇花費最少的方案 把結果，就是...
動態規劃練習題及解答
題1 多公尺諾骨牌 domino 問題描述 有一種多公尺諾骨牌是平面的，其正面被分成上下兩部分，每一部分的表面或者為空，或者被標上1至6個點。現有一行排列在桌面上 頂行骨牌的點數之和為6 1 1 1 9 底行骨牌點數之和為1 5 3 2 11。頂行和底行的差值是2。這個差值是兩行點數之和的差的絕對值...
動態規劃第一部分
近年來，涉及動態規劃的各種競賽題越來越多，每一年的noi幾乎都至少有一道題目需要用動態規劃的方法來解決 而競賽對選手運用動態規劃知識的要求也越來越高，已經不再停留於簡單的遞推和建模上了。要了解動態規劃的概念，首先要知道什麼是多階段決策問題。一 多階段決策問題 如果一類活動過程可以分為若干個互相聯絡的...