動態(tài)規(guī)劃：NOIP的題目

1、順序?qū)R源程序名ALIGN.?(PAS, C, CPP)可執(zhí)行文件名ALIGN.EXE輸入文件名ALIGN.IN輸出文件名ALIGN.OUT考慮兩個字符串右對齊的最佳解法。例如，有一個右對齊方案中字符串是AADDEFGGHC 和 ADCDEGHoAAD_DEFGGHCADCDE_GH_每一個數(shù)值匹配的位置值2分，一段連續(xù)的空格值-1分。所以總分是匹配點的2倍減 去連續(xù)空格的段數(shù)，在上述給定的例子中，6個位置(A,D,D,E,G,H)匹配，三段空格，所以 得分2*6+(-1)*3=9,注意，我們并不處罰左邊的不匹配位置。若匹配的位置是兩個不同的 字符，則既不得分也不失分。請你寫個程序找出最佳右對

2、齊方案。輸入輸入文件包含兩行，每行一個字符串，最長50個字符。字符全部是大字字母。輸出一行，為最佳對齊的得分。樣例ALIGN.INAADDEFGGHCADCDEGHALIGN.OUT9任務(wù)安排源程序名BATCH.?(PAS, C,CPP)可執(zhí)行文件名BATCH.EXE輸入文件名BATCH.IN輸出文件名BATCH.OUTN個任務(wù)排成一個序列在一臺機器上等待完成(順序不得改變)，這N個任務(wù)被分成若 干批，每批包含相鄰的若干任務(wù)。從時刻0開始，這些任務(wù)被分批加工，第i個任務(wù)單獨完 成所需的時間是4。在每批任務(wù)開始前，機器需要啟動時間S，而完成這批任務(wù)所需的時間 是各個任務(wù)需要時間的總和(同一批任務(wù)

3、將在同一時刻完成)。每個任務(wù)的費用是它的完成 時刻乘以一個費用系數(shù)巨。請確定一個分組方案，使得總費用最小。例如：S=1； T=1,3,4,2,1； F=3,2,3,3,4。如果分組方案是1,2、3、4,5，則 完成時間分別為5,5,10,14,14，費用C=15,10,30,42,56，總費用就是153。輸入第一行是 N(1=N=5000)。第二行是 S(0=S=50)。下面N行每行有一對數(shù)，分別為二和七均為不大于100的正整數(shù)，表示第i個任務(wù) 單獨完成所需的時間是二及其費用系數(shù)F、1輸出一個數(shù)，最小的總費用。樣例BATCH.IN51 TOC o 1-5 h z 3 HYPERLINK l b

4、ookmark349 o Current Document 23 HYPERLINK l bookmark205 o Current Document 31 4BATCH.OUT153最大的算式源程序名BIGEXP.?(PAS, C, CPP)可執(zhí)行文件名BIGEXP.EXE輸入文件名BIGEXP.IN輸出文件名BIGEXP.OUT題目很簡單，給出N個數(shù)字，不改變它們的相對位置，在中間加入K個乘號和N-K-1 個加號，(括號隨便加)使最終結(jié)果盡量大。因為乘號和加號一共就是N-1個了，所以恰好 每兩個相鄰數(shù)字之間都有一個符號。例如：N=5, K=2，5個數(shù)字分別為1、2、3、4、5，可以加成：1

5、*2*(3+4+5)=241*(2+3)*(4+5)=45(1*2+3)*(4+5)=45輸入輸入文件共有二行，第一行為兩個有空格隔開的整數(shù)，表示N和K，其中(2=N=15, 0=K=N-1)。第二行為N個用空格隔開的數(shù)字(每個數(shù)字在0到9之間)。輸出輸出文件僅一行包含一個整數(shù)，表示要求的最大的結(jié)果樣例BIGEXP.IN 5 2 1 2 3 4 5BIGEXP.OUT 120說明(1+2+3)*4*5=120BLAST源程序名BLAST.?(PAS, C, CPP)可執(zhí)行文件名BLAST.EXE輸入文件名BLAST.IN輸出文件名BLAST.OUT設(shè)有字符串X，我們稱在X的頭尾及中間插入任意多

6、個空格后構(gòu)成的新字符串為X的擴 展串，如字符串 X 為 “abcbcd”，則字符串a(chǎn)bcbcd”，“OaObcbcdO ”和 “abcbcd口” 都是X的擴展串，這里“口”代表空格字符。如果A1是字符串A的擴展串，B1是字符串B的擴展串，&與B1具有相同的長度，那么 我們定義字符串A1與B/勺距離為相應(yīng)位置上的字符的距離總和，而兩個非空格字符的距離 定義為它們的ascIi碼的差的絕對值，而空格字符與其它任意字符之間的距離為已知的定值 K，空格字符與空格字符的距離為O。在字符串A、B的所有擴展串中，必定存在兩個等長的 擴展串A1. B1，使得A1與B1之間的距離達到最小，我們將這一距離定義為字符

7、串A、B的距 離。1請你寫一個程序，求出字符串A、B的距離。輸入輸入文件第一行為字符串A，第二行為字符串B，A、B均由小寫字母組成且長度均不超 過2000，第三行為一個整數(shù)K，1WKW100，表示空格與其它字符的距離。輸出輸出文件僅一行包含一個整數(shù)，表示要求的字符串A、B的距離。樣例BLAST.INcmcsnmn2BLAST.OUT10書的復(fù)制源程序名BOOK.?(PAS,C, CPP)可執(zhí)行文件名BOOK.EXE輸入文件名BOOK.IN輸出文件名BOOK.OUT現(xiàn)在要把M本有順序的書分給K個人復(fù)制(抄寫)，每一個人的抄寫速度都一樣，一本 書不允許給兩個(或以上)的人抄寫，分給每一個人的書，必

8、須是連續(xù)的，比如不能把第一、 第三、第四本數(shù)給同一個人抄寫。現(xiàn)在請你設(shè)計一種方案，使得復(fù)制時間最短。復(fù)制時間為 抄寫頁數(shù)最多的人用去的時間。輸入第一行兩個整數(shù)M、K；(K=M=100)第二行M個整數(shù)，第i個整數(shù)表示第i本書的頁數(shù)。輸出共K行，每行兩個正整數(shù)，第i行表示第i個人抄寫的書的起始編號和終止編號。K行 的起始編號應(yīng)該從小到大排列，如果有多解，則盡可能讓前面的人少抄寫。樣例BOOK.IN9 31 2 3 4 5 6 7 8 9BOOK.OUT1 56 78 9最小乘車費用源程序名BUSSES.? (PAS, C, CPP)可執(zhí)行文件名BUSSES.EXE輸入文件名BUSSES.IN輸出文

9、件名BUSSES.OUT某條街上每一公里就有一汽車站，乘車費用如下表:公里數(shù)12345678910費用122131404958697990101而一輛汽車從不行駛超過10公里。某人想行駛n公里，假設(shè)他可以任意次換車，請你 幫他找到一種乘車方案使費用最小(10公里的費用比1公里小的情況是允許的)。編一程序：從文件BUSSES.IN中讀入對乘車費用的描述；算出最小的價格；把結(jié)果寫入文件BUSSES.OUT中。輸入輸入文件共兩行，第一行為10個不超過100的整數(shù)，依次表示行駛110公里的費用， 相鄰兩數(shù)間用空格隔開；第二行為某人想要行駛的公里數(shù)。輸出輸出文件僅一行包含一個整數(shù)，表示該測試點的最小費用

10、。樣例BUSSES.IN12 21 31 40 49 58 69 79 90 10115BUSSES.OUT147筷子源程序名CHOP.?(PAS, C, CPP)可執(zhí)行文件名CHOP.EXE輸入文件名CHOP.IN輸出文件名CHOP.OUTA先生有很多雙筷子。確切的說應(yīng)該是很多根，因為筷子的長度不一，很難判斷出哪兩 根是一雙的。這天，A先生家里來了 K個客人，A先生留下他們吃晚飯。加上A先生，A夫 人和他們的孩子小A，共K+3個人。每人需要用一雙筷子。A先生只好清理了一下筷子，共 N根，長度為T1,T2,T3,TN.現(xiàn)在他想用這些筷子組合成K+3雙，使每雙的筷子長度差 的平方和最小。(怎么不

11、是和最?。窟@要去問A先生了，呵呵)輸入輸入文件共有兩行，第一行為兩個用空格隔開的整數(shù)，表示N,K(1WNW100, 0K50)， 第二行共有N個用空格隔開的整數(shù)，為Ti.每個整數(shù)為150之間的數(shù)。輸出輸出文件僅一行。如果湊不齊K+3雙，輸出-1,否則輸出長度差平方和的最小值。樣例CHOP.IN10 11 1 2 3 3 3 4 6 10 20CHOP.OUT5說明第一雙1 1第二雙2 3第三雙3 3第四雙4 6（1-1廣2+（2-3廣2+（3-3廣2+（4-6廣2=5護衛(wèi)隊源程序名CONVOY.?（PAS, C, CPP）可執(zhí)行文件名CONVOY.EXE輸入文件名CONVOY.IN輸出文件名C

12、ONVOY.OUT護衛(wèi)車隊在一條單行的街道前排成一隊，前面河上是一座單行的橋。因為街道是一條 單行道，所以任何車輛都不能超車。橋能承受一個給定的最大承載量。為了控制橋上的交通， 橋兩邊各站一個指揮員。護衛(wèi)車隊被分成幾個組，每組中的車輛都能同時通過該橋。當一組 車隊到達了橋的另一端，該端的指揮員就用電話通知另一端的指揮員，這樣下一組車隊才能 開始通過該橋。每輛車的重量是已知的。任何一組車隊的重量之和不能超過橋的最大承重量。 被分在同一組的每一輛車都以其最快的速度通過該橋。一組車隊通過該橋的時間是用該車隊 中速度最慢的車通過該橋所需的時間來表示的。問題要求計算出全部護衛(wèi)車隊通過該橋所需 的最短時間

13、值。輸入輸入文件第一行包含三個正整數(shù)（用空格隔開），第一個整數(shù)表示該橋所能承受的最大 載重量（用噸表示）；第二個整數(shù)表示該橋的長度（用千米表示）；第三個整數(shù)表示該護衛(wèi)隊中 車輛的總數(shù)（n1000）。接下來的幾行中，每行包含兩個正整數(shù)W和S （用空格隔開），W表示 該車的重量（用噸表示），S表示該車過橋能達到的最快速度（用千米/小時表示）。車子的重 量和速度是按車子排隊等候時的順序給出的。輸出輸出文件應(yīng)該是一個實數(shù)，四舍五入精確到小數(shù)點后1位，表示整個護衛(wèi)車隊通過該橋所需的最短時間（用分鐘表示）。樣例 CONVOY.IN 100 5 10 40 25 50 20 50 20 70 10 12 5

14、0 9 70 49 30 38 25 27 50 19 70CONVOY.OUT 75.0DOLLARS源程序名DOLLARS.?(PAS, C,CPP)可執(zhí)行文件名DOLLARS.EXE輸入文件名DOLLARS.IN輸出文件名DOLLARS.OUT在以后的若干天里戴維將學(xué)習(xí)美元與德國馬克的匯率。編寫程序幫助戴維何時應(yīng)買或賣 馬克或美元，使他從100美元開始，最后能獲得最高可能的價值。輸入輸入文件的第一行是一個自然數(shù)N, 1WNW100,表示戴維學(xué)習(xí)匯率的天數(shù)。接下來的N行中每行是一個自然數(shù)A, 1WAW1000。第i+1行的A表示預(yù)先知道的第i+1 天的平均匯率，在這一天中，戴維既能用100

15、美元買A馬克也能用A馬克購買100美元。輸出輸出文件的第一行也是唯一的一行應(yīng)輸出要求的錢數(shù)(單位為美元，保留兩位小數(shù))。注意：考慮到實數(shù)算術(shù)運算中進位的誤差，結(jié)果在正確結(jié)果0.05美元范圍內(nèi)的被認為 是正確的，戴維必須在最后一天結(jié)束之前將他的錢都換成美元。樣例DOLLARS.IN5400300500300250DOLLARS.OUT266.66樣例解釋（無需輸出）Day 1.changing100.0000美元=400.0000馬克Day 2.changing400.0000馬克=133.3333美元Day 3.changing133.3333美元=666.6666馬克Day 5.changi

16、ng666.6666馬克=266.6666美元動態(tài)規(guī)劃部分（初中組不作要求）潛水員（gas.exe）潛水員為了潛水要使用特殊的裝備。他有一個帶2種氣體的氣缸：一個為氧 氣，一個為氮氣。讓潛水員下潛的深度需要各種的數(shù)量的氧和氮。潛水員有一定 數(shù)量的氣缸。每個氣缸都有重量和氣體容量。潛水員為了完成他的工作需要特定 數(shù)量的氧和氮。他完成工作所需氣缸的總重的最低限度的是多少？例如：潛水員有5個氣缸。每行三個數(shù)字為：氧，氮的（升）量和氣缸的重 量：36 12010 25 1295 50 2501 45 13020 119如果潛水員需要5升的氧和60升的氮則總重最小為249 （1，2或者4, 5 號氣缸）

17、。你的任務(wù)就是計算潛水員為了完成他的工作需要的氣缸的重量的最低值。輸入格式從文本文件gas.in中讀入數(shù)據(jù)。第一行有2整數(shù)t，a（1=t=21，1=a=79）。它們表示氧，氮各自需要的 量。第二行為整數(shù)n (1=n=1000)表示氣缸的個數(shù)。此后的 n 行，每行包括 ti, ai, wi (1=ti=21, 1=ai=79, 1=wi=800) 3 整數(shù)。這些各自是：第i個氣缸里的氧和氮的容量及汽缸重量。輸出格式僅一行包含一個整數(shù)，為潛水員完成工作所需的氣缸的重量總和的最低值。樣例輸入60536 12010 25 1295 50 2501 45 13020 119樣例輸出249饑餓的奶牛(hu

18、nger.exe)John養(yǎng)了若干奶牛，每天晚上奶牛都要進食。由于條件比較簡陋，并不一 定所有奶牛都能吃到食物。奶牛的進食方式是這樣的：John有n個食桶(1=n=2000)，分別編號為1.n。這些食桶被按照編號排成一行。John將奶牛 們分成若干組，每組奶?？偸谴粼谝黄疬M食的，每組奶牛會提出要求他們需 要吃第start到第end桶中的食物?？赡艽嬖谌舾山M奶牛都要吃同一個桶中的食 物，從而就產(chǎn)生了沖突，這時John只能滿足其中一組的要求，另一些組就只能 餓肚子了。John當然不想讓奶牛都餓肚子，所以他希望根據(jù)奶牛們提出的請求，滿足 其中一些組的要求，使得最多的食桶被奶牛食用。這個難題困擾著Jo

19、hn，他希 望得到你的幫助。輸入格式從文本文件hunger.in中讀入數(shù)據(jù)。第一行一個整數(shù)n，表示奶牛的組數(shù)。(1=n=1000)第2n+1行，每行兩個整數(shù)start和end，描述了一組奶牛提出的請求。輸出格式一個整數(shù)，表示最多有多少個食桶可以被食用。樣例輸入31 37 83 4樣例輸出5（滿足第1組和第2組奶牛的要求，這樣13號和78號這5個食桶可以被食用）單詞的劃分（word.exe）有一個很長的由小寫字母組成字符串。為了便于對這個字符串進行分析，需 要將它劃分成若十個部分，每個部分稱為一個單詞。出于減少分析量的目的，我 們希望劃分出的單詞數(shù)越少越好。你就是來完成這一劃分工作的。輸入格式從

20、文本文件word.in中讀入數(shù)據(jù)。第一行，一個字符串。（字符串的長度不超過100）第二行一個整數(shù)n，表示單詞的個數(shù)。（n=100）第3n+2行，每行列出一個單詞。輸出格式一個整數(shù)，表示字符串可以被劃分成的最少的單詞數(shù)。樣例輸入realityour5realrealityityourour樣例輸出2（原字符串可拆成real+it+your或reality+our，由于reality+our僅為兩個部分， 因此最優(yōu)解為2,另外注意，單詞列表中的每個單詞都可以重復(fù)使用多次，也可 以不用）火車票(railway.exe)從Ekaterinburg到Sverdlovsk的火車線路上有若干個站點。這條線路

21、可以近 似的表示為一條線段，火車站就是線段上的點。線路始于 Ekaterinburg，終于 Sverdlovsko Ekaterinburg被標號為1，Sverdlovsk被標號為n。(n為整條線路上 的站點數(shù))線路上的任意兩個站點間的直達票價是由它們間的距離決定的，票價根據(jù)以 下規(guī)則制定：X為兩站的距離價格0Xv=L1C1L1vXv=L2C2L2vXv=L3C3如果兩站的間距超過L3,則無直達車票。所以有時可能有必要買多張票，通過 轉(zhuǎn)車的方式，從一個站到達另一個站。例如，在上面的圖中，有7個站點。2號站點到6號站點的距離超過L3, 不能買直達票。存在若干種中轉(zhuǎn)的方法，其中的一種是買兩張票：先

22、花費C2從 2號站到達3號站，然后花費C3從3號站到6號站，一種花費C2+C3。你的任務(wù)是，找出一種最經(jīng)濟的中轉(zhuǎn)方案。輸入格式從文本文件railway.in中讀入數(shù)據(jù)。第一行 6 個整數(shù) L1, L2, L3, C1, C2, C3 ( 1=L1L2L3=10A9, 1v=C1vC2vC3v=10人9)，中間用空格分隔。第二行一個整數(shù)n(2v=nv=100)，表示線路上的車站數(shù)。第三行兩個整數(shù)s和t，分別是起點和終點的編號。注意：s不一定小于t。以下的n-1行，按據(jù)Ekaterinburg遠近，每行描述了一個車站的位置。它包 含一個整數(shù)，表示該車站據(jù)Ekaterinburg的距離。任意兩個車站

23、的距離不超過10A9，任意兩個相鄰的車站的距離不超過L3。輸出格式一個整數(shù)，表示從給定的一個站到給定的另一個站的最小花費。樣例輸入3 6 8 20 30 4072 6378131523樣例輸出70加油問題（oil.exe）一個美國旅行代理上經(jīng)常被要求去估計開車從一個城市旅行至另一個城市 的最小費用。他有一個在通常路線上的大多數(shù)加油站的列表。列表包括了所有加 油站的位置及當前每加侖汽油的價格。為了簡化估計費用的過程，代理商使用了以下的簡化汽車駕駛員行為的規(guī) 則：除非汽車無法用油箱里的汽油達到下一個加油站（如果有的話）或目的地， 在油箱里還有不少于最大容量一半的汽油時，駕駛員從不在加油站停下 來。

24、在每一個停下的加油站，駕駛員總是將油加滿。在一個加油站停下之后，駕駛員將為旅程在快餐和糖果上花去2.00元。在駛向加油站或目的地時，駕駛員不需要超過必須量的汽油。不需要“安 全余量”。駕駛員開始旅行時油箱總是滿的每個加油站付款時四舍五入到分（1元等于100分）。你必須寫一個程序以估計駕駛員在旅程上至少要為汽油和食品付多少錢。輸入格式從文本文件oil.in中讀入數(shù)據(jù)。開始的2行給出了出發(fā)地和目的地的信息。數(shù)據(jù)項的后繼行代表了路線上的 加油站，每個加油站用一行表示。下面是輸入數(shù)據(jù)中數(shù)據(jù)項的精確格式及其含義。第一行：一個實數(shù)一一從出發(fā)地到目的地的距離（英里）第二行：三個實數(shù)及一個整數(shù)第一個實數(shù)是汽車

25、油箱的最大的容量（加侖）第二個實數(shù)是汽車每加侖汽油可以行駛的英里數(shù)第三個實數(shù)是汽車在出發(fā)地城市加滿油箱的費用（單位：元）整數(shù)（小于51）是路線上加油站的數(shù)目接下來的每一行：兩個實數(shù)第一個實數(shù)是從出發(fā)地到加油站的距離（單位：英里）第二個實數(shù)是該加油站出售的汽油每加侖的價格（單位：分）數(shù)據(jù)項中的所有數(shù)據(jù)都是正的。一條路線上的加油站根據(jù)其到出發(fā)地的距離 遞增排列。路線上不存在這樣的加油站，它到出發(fā)點的距離大于從出發(fā)點到目的 地的距離。每條路線上的加油站都被適當?shù)陌才乓允沟萌魏纹嚩寄軓某霭l(fā)地開 到目的地。輸出格式僅一行，一個實數(shù)（保留兩位小數(shù)），表示最小的花費（單位：元）。樣例輸入475.611.9

26、 27.4 14.98 6102.0 99.9220.0 132.9256.3 147.9275.0 102.9277.6 112.9381.8 100.9樣例輸出27.31公路乘車（buses.exe）一個特別的單行街道在每公里處有一個汽車站。顧客根據(jù)他們乘坐汽車的公 里使來付費。例如下表就是一個費用的單子。Kilometres12345618910Price12213140牯58697990101沒有一輛車子行駛超過10公里，一個顧客打算行駛n公里（1=n=100），它可 以通過無限次的換車來完成旅程。最后要求費用最少。輸入格式第一行十個整數(shù)分別表示行走1到10公里的費用（ in和inpu

27、t”)。輸入n個字符串，長度不超過200,表示一句句子。如果可能是那兩個人的 對話，則輸出”YES”；否則，輸出”NO”。輸入格式第一行一個整數(shù)n，表示一共有n句句子。此后每行一個字符串，表示一句句子。輸出格式n行，每行一個”YES”或”NO”，表示你的判斷結(jié)果。樣例輸入6putoninonputinoneputonininputoutoutputoneininputwooutoutputoutpuutput樣例輸出YESNOYESNONONO觀光游覽（view.exe）一條街道被分成m格（1=m=100）,還有n個景點（1=n=100）,分布在 街道上。每個景點可以占據(jù)連續(xù)的若干格，并且有一

28、個美學(xué)值v（0v=100）。 現(xiàn)要組織k個人考察這個街道（1=k=m），每個人考察的區(qū)域是連續(xù)的若干格 （不可為0格），且任意兩個人考察的區(qū)域不得相交，也不得有一個格子無人考 察。對于任意一個人，如果它考察的區(qū)域中有一個風景點（風景點必須完整的位 于這個區(qū)域），則它就得到了這個風景點的分值（美學(xué)值）。你的任務(wù)是將街道的m個格子分給k個人去考察，使得總的分值最大。輸入格式第一行一個整數(shù)m，表示街道的長度。第二行一個整數(shù)n，表示風景點個數(shù)。此后n行，每行描述一個風景點，三個整數(shù)x、y和v，表示該風景點是從 第x個格子到第y個格子，美學(xué)值為v。最后一行一個整數(shù)k，表示考察的人數(shù)。輸出格式一個整數(shù)，表

29、示最大可以得到的分值。樣例輸入322 23 32樣例輸出3胖男孩源程序名FATBOY.?（PAS, C, CPP）可執(zhí)行文件名FATBOY.EXE輸入文件名FATBOY.IN輸出文件名FATBOY.OUT麥克正如我們所知的已快樂地結(jié)婚，在上個月他胖了 70磅。因為手指上的脂肪過多， 使他連給他最親密的朋友斯拉夫克寫一個電子郵件都很困難。每晚麥克都詳細地描述那一天他所吃的所有東西，但有時當他只想按一次某鍵時往往會 按了不止一次，并且他的胖手指還會碰到他不想要按的鍵，麥克也知道自己的手指有問題， 因此他在打字的時候很小心，以確保每打一個想要的字符時誤打的字符不超過3個，誤打的 字符可能在正確字符之

30、前也可能在其之后。當斯拉夫克多次收到讀不懂的電子郵件后，他總是要求麥克將電子郵件發(fā)3遍，使他容 易讀懂一點。編寫程序，幫助斯拉夫克根據(jù)他所收到的三封電子郵件求出麥克可能寫出的最長的信。輸入輸入文件包含了三行文本。每一行文本包括麥克信件的一種版本。其中所有的字符都由 英文字母表中的小寫字母組成并且不超過100個。輸出輸出文件中第一行即唯一的一行數(shù)據(jù)應(yīng)該包含斯拉夫克根據(jù)所收到的電子郵件推測出 的最長信件。你可以相信問題一定有解，但解不一定是唯一的。樣例FATBOY.INcecqbhvaiaedpibalukcabegviapcihlaaugckadceevfdadaepcialaukdFATBOY

31、.OUTcevapiluk文件排版源程序名FORMAT.?(PAS, C, CPP)可執(zhí)行文件名FORMAT.EXE輸入文件名FORMAT.IN輸出文件名FORMAT.OUT寫電子郵件是有趣的，但不幸的是經(jīng)常寫不好看，主要是因為所有的行不一樣長，你的 上司想要發(fā)排版精美的電子郵件，你的任務(wù)是為他編寫一個電子郵件排版程序。完成這個任務(wù)最簡單的辦法是在太短的行中的單詞之間插入空格，但這并不是最好的方法， 考慮如下例子：個個個個個個個個個個個個個個個個個個個個個個個個個個個個This is the example you areactually considering.假設(shè)我們想將第二行變得和第一行

32、一樣長，靠簡單地插入空格則我們將得到如下結(jié)果:個個個個個個個個個個個個個個個個個個個個個個個個個個個個This is the example you areactuallyconsidering.但這太難看了，因為在第二行中有一個非常大的空白，如果將第一行的單詞“are”移 到下一行我們將得到較好的結(jié)果： 個*This is the example youare actually considering.當然，這必須對難看程度進行量化。因此我們必須給出單詞之間的空格的難看程度，一 個包含N個空格符的空白段，其難看程度值為(n-1)2程序的目的是使難看程度的總和最小 化。例如，第一個例子的難看程

33、度是1+7*7=50，而第二個例子的難看程度僅為 1+1+1+4+1+4=12。輸出時，每一行的開頭和結(jié)尾處都必須是一個單詞，即每行開頭和結(jié)尾處不能有空白。唯一 例外的是該行僅有一個單詞組成的情況，對于這種情況你可將單詞放在該行開頭處輸出，此 時如果該單詞比該行應(yīng)有的長度短則我們指定它的最壞程度為500，當然在這種情況下，該 行的實際長度即為該單詞的長度。輸入輸入文件第一行是一個整數(shù)N，表示該段要求達到的寬度，1=N=80。該段文章由一個 或多個單詞組成，單詞由ASCII碼值為33到126 (包含33和126)的字符組成，單詞與單 詞之間用空格隔開(可能超過一個)。單詞長度不會超過段落要求達到

34、的寬度。一段文字所 有單詞的總長度不會超過10000個字符，任何一行都不會超過100個字符，任何一個單詞都 在同一行內(nèi)。輸出對于每個段落，找出使其難看程度最小的排版形式并輸出句子：“Minimal badness is B. ”，B是指按可能的最好排版形式會發(fā)生的難看程度值。注意排版后文本行數(shù)任意，多余 的空格也可刪除。樣例FORMAT.IN28This is the example you are actually considering.FORMAT.OUTMinimal badness is 12.相似基因源程序名GENE.?(PAS, C, CPP)可執(zhí)行文件名GENE.EXE輸入文件

35、名GENE.IN輸出文件名GENE.OUT大家都知道，基因可以看作一個堿基對序列。它包含了 4種核苷酸，簡記作A,C,G,T。生物學(xué)家正致力于尋找人類基因的功能，以利用于診斷疾病和發(fā)明藥物。在一個人類基因工作組的任務(wù)中，生物學(xué)家研究的是：兩個基因的相似程度。因為這 個研究對疾病的治療有著非同尋常的作用。兩個基因的相似度的計算方法如下：對于兩個已知基因，例如AGTGATG和GTTAG，將它們的堿基互相對應(yīng)。當然，中間可以 加入一些空堿基-，例如：AGTGAT-G-GT-TAG這樣,兩個基因之間的相似度就可以用堿基之間相似度的總和來描述，堿基之間的相似 度如下表所示：那么相似度就是：(-3)+5+

36、5+(-2) + (-3)+5+(-3)+5=9。因為兩個基因的對應(yīng)方法不唯一， 例如又有：AGTGATG-GTTA-G相似度為：(-3)+5+5+(-2)+5+(-1)+5=14。規(guī)定兩個基因的相似度為所有對應(yīng)方法中， 相似度最大的那個。輸入共兩行。每行首先是一個整數(shù)，表示基因的長度；隔一個空格后是一個基因序列，序 列中只含A,C,G,T四個字母。1=序列的長度=100。輸出僅一行，即輸入基因的相似度。樣例GENE.INAGTGATG5 GTTAGGENE.OUT14饑餓的牛源程序名HUNGER.?(PAS, C,CPP)可執(zhí)行文件名HUNGER.EXE輸入文件名HUNGER.IN輸出文件名

37、HUNGER.OUT牛在飼料槽前排好了隊。飼料槽依次用1到N(1=N=2000)編號。每天晚上，一頭幸運 的牛根據(jù)約翰的規(guī)則，吃其中一些槽里的飼料。約翰提供B個區(qū)間的清單。一個區(qū)間是一對整數(shù)start-end,1=start=end=N，表示 一些連續(xù)的飼料槽，比如1-3,7-8,3-4等等。?？梢匀我膺x擇區(qū)間，但是牛選擇的區(qū)間不能 有重疊。當然，牛希望自己能夠吃得越多越好。給出一些區(qū)間，幫助這只牛找一些區(qū)間，使它能 吃到最多的東西。在上面的例子中，1-3和3-4是重疊的；聰明的牛選擇1-3, 7-8，這樣可以吃到5個 槽里的東西。輸入第一行，整數(shù) B(1=B=1000)第2到B+1行，每行兩

38、個整數(shù)，表示一個區(qū)間，較小的端點在前面。輸出僅一個整數(shù)，表示最多能吃到多少個槽里的食物。樣例HUNGER.IN31 384HUNGER.OUT5匹1=1遞增序列(INCNEASING SEQUENCES)源程序名INCSQ.?(PAS, C,CPP)可執(zhí)行文件名INCSQ.EXE輸入文件名INCSQ.IN輸出文件名INCSQ.OUT給定一個數(shù)字串，請你插入若干個逗號，使得該數(shù)字串成為一個嚴格遞增的數(shù)列且最后 一個數(shù)要盡可能小，在這個問題中，前導(dǎo)的零是允許出現(xiàn)在數(shù)的前面的。輸入輸入數(shù)據(jù)僅含一行，為一個長度不超過80的數(shù)字串。輸出輸出一個嚴格遞增且最后一數(shù)最小的數(shù)列，相鄰兩個數(shù)之間用一個逗號隔開，

39、如果有多 個數(shù)列滿足要求，則輸出第一個數(shù)最大的那個數(shù)列，若這樣的解還不止一個，則輸出第二個 數(shù)最大的那個數(shù)列，以此類推。樣例INCSQ.IN100000101INCSQ.OUT100,000101奇怪的電梯源程序名LIFT.?(PAS,C, CPP)可執(zhí)行文件名LIFT.EXE輸入文件名LIFT.IN輸出文件名LIFT.OUT呵呵，有一天我做了一個夢，夢見了一種很奇怪的電梯。大樓的每一層樓都可以停電梯， 而且第i層樓(1=i=N)上有一個數(shù)字Ki(0=Ki=N)。電梯只有四個按鈕：開，關(guān)，上，下。 上下的層數(shù)等于當前樓層上的那個數(shù)字。當然，如果不能滿足要求，相應(yīng)的按鈕就會失靈。 例如：3 3

40、1 2 5代表了 Ki(K1=3,K2=3,)，從一樓開始。在一樓，按“上”可以到4 樓，按“下”是不起作用的，因為沒有-2樓。那么，從A樓到B樓至少要按幾次按鈕呢？輸入輸入文件共有二行，第一行為三個用空格隔開的正整數(shù)，表示N,A,B(1WNW200,1WA,BWN)，第二行為N個用空格隔開的正整數(shù)，表示Ki。輸出輸出文件僅一行，即最少按鍵次數(shù)，若無法到達，則輸出-1。樣例LIFT.IN5 1 53 3 1 2 5LIFT.OUT3LIGNJA源程序名LIGNJA.?(PAS, C, CPP)可執(zhí)行文件名LIGNJA.EXE輸入文件名LIGNJA.IN輸出文件名LIGNJA.OUT尼克每天上班

41、之前都連接上英特網(wǎng)，接收他的上司發(fā)來的郵件，這些郵件包含了尼克主 管的部門當天要完成的全部任務(wù)，每個任務(wù)由一個開始時刻與一個持續(xù)時間構(gòu)成。尼克的一個工作日為N分鐘，從第一分鐘開始到第N分鐘結(jié)束。當尼克到達單位后他就 開始干活。如果在同一時刻有多個任務(wù)需要完成，尼克可以任選其中的一個來做，而其余的 則由他的同事完成，反之如果只有一個任務(wù)，則該任務(wù)必需由尼克去寫成，假如某些任務(wù)開 始時刻尼克正在工作，則這些任務(wù)也由尼克的同事完成。如果某任務(wù)于第P分鐘開始，持續(xù) 時間為T分鐘，則該任務(wù)將在第P+T-1分鐘結(jié)束。寫一個程序計算尼克應(yīng)該如何選取任務(wù)，才能獲得最大的空暇時間。輸入輸入數(shù)據(jù)第一行包含兩個用空

42、格隔開的整數(shù)N和K，1WNW10000，1WKW10000，N表 示尼克的工作時間，單位為分，K表示任務(wù)總數(shù)。接下來共有K行，每一行有兩個用空格隔開的整數(shù)P和T，表示該任務(wù)從第P分鐘開始， 持續(xù)時間為T分鐘，其中1WPWN，1WP+T-1WN。輸出輸出文件僅一行包含一個整數(shù)表示尼克可能獲得的最大空暇時間。樣例LIGNJA.IN15 61 2611515LIGNJA.OUT4POLYGON源程序名POLYGON.? (PAS, C, CPP)可執(zhí)行文件名POLYGON.EXE輸入文件名POLYGON.IN輸出文件名POLYGON.OUT對于一個多邊形來說，在該多邊形內(nèi)任取兩點，如果這兩點連成的線

43、段落在多邊形內(nèi)， 則稱這樣的多邊形為凸多邊形。平面上有N個坐標值為自然數(shù)的圓點。頂點數(shù)最多凸多邊形是指由給定的圓點中的一 部分組成的凸多邊形，它包含最大可能的頂點數(shù)。原點，即坐標內(nèi)中心(0，0)必須是頂點數(shù) 最多凸多邊形的一個頂點。編寫程序求出這樣的凸多邊形的最大頂點數(shù)。注意一個多邊形的連續(xù)的邊不能是平行 的。輸入輸入文件的第一行包含一個自然數(shù)N，2WNW100，表示給定的圓點數(shù)。下面的N行每行包含兩個用空格隔開的自然數(shù)X和Y，1WXW100，1WYW100，表示一 個圓點的坐標值。所有的圓點是不相同的。輸出輸出文件的第一行也是唯一的一行應(yīng)該包含頂點數(shù)最多凸多邊形的頂點數(shù)。注意結(jié)果 應(yīng)不小于3。樣例POLYGON.IN810 83 92 82 321038 10POLYGON.OUT8POWER源程序名P