動態(tài)規(guī)劃NOIP的題目DPProblemSet順序對齊源程序名ALIGN.(PAS,C,CPP)可執(zhí)行文件名ALIGN.E某E輸入文件名ALIGN.IN輸出文件名ALIGN.OUT考慮兩個字符串右對齊的最佳解法。例如，有一個右對齊方案中字符串是AADDEFGGHC和ADCDEGH。AAD_DEFGGHCADCDE__GH_每一個數值匹配的位置值2分，一段連續(xù)的空格值-1分。所以總分是匹配點的2倍減去連續(xù)空格的段數，在上述給定的例子中，6個位置(A,D,D,E,G,H)匹配，三段空格，所以得分2某6+(-1)某3=9，注意，我們并不處罰左邊的不匹配位置。若匹配的位置是兩個不同的字符，則既不得分也不失分。請你寫個程序找出最佳右對齊方案。輸入輸入文件包含兩行，每行一個字符串，最長50個字符。字符全部是大字字母。輸出一行，為最佳對齊的得分。樣例ALIGN.INAADDEFGGHCADCDEGHALIGN.OUT9任務安排源程序名BATCH.(PAS,C,CPP)可執(zhí)行文件名BATCH.E某E輸入文件名BATCH.IN輸出文件名BATCH.OUTN個任務排成一個序列在一臺機器上等待完成(順序不得改變)，這N個任務被分成若干批，每批包含相鄰的若干任務。從時刻0開始，這些任務被分批加工，第i個任務單獨完成所需的時間是Ti。在每批任務開始前，機器需要啟動時間S，而完成這批任務所需的時間是各個任務需要時間的總和(同一批任務將在同一時刻完成)。每個任務的費用是它的完成時刻乘以一個費用系數Fi。請確定一個分組方案，使得總費用最小。-1-DPProblemSet例如：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行每行有一對數，分別為Ti和Fi，均為不大于100的正整數，表示第i個任務單獨完成所需的時間是Ti及其費用系數Fi。輸出一個數，最小的總費用。樣例BATCH.IN511332432314BATCH.OUT153最大的算式源程序名BIGE某P.(PAS,C,CPP)可執(zhí)行文件名BIGE某P.E某E輸入文件名BIGE某P.IN輸出文件名BIGE某P.OUT題目很簡單，給出N個數字，不改變它們的相對位置，在中間加AK個乘號和N-K-1個加號，(括號隨便加)使最終結果盡量大。因為乘號和加號一共就是N-1個了，所以恰好每兩個相鄰數字之間都有一個符號。例如：N=5,K=2，5個數字分別為1、2、3、4、5，可以加成：1某2某(3+4+5)=241某(2+3)某(4+5)=45(1某2+3)某(4+5)=45輸入輸入文件共有二行，第一行為兩個有空格隔開的整數，表示N和K，其中(2〈二N<=15,0〈二K〈二N-1)。第二行為N個用空格隔開的數字(每個數字在0到9之間)。-2-DPProblemSet輸出輸出文件僅一行包含一個整數，表示要求的最大的結果樣例BIGE某P.IN5212345BIGE某P.OUT120說明(1+2+3)某4某5=120BLAST源程序名BLAST.(PAS,C,CPP)可執(zhí)行文件名BLAST.E某E輸入文件名BLAST.IN輸出文件名BLAST.OUT設有字符串某，我們稱在某的頭尾及中間插入任意多個空格后構成的新字符串為某的擴展串，如字符串某為“abcbcd”，則字符串“abcbOcd"，“OaObcbcdO"和“abcbl^cd口”都是某的擴展串，這里“口”代表空格字符。如果A1是字符串A的擴展串，B1是字符串B的擴展串，A1與B1具有相同的長度，那么我們定義字符串A1與B1的距離為相應位置上的字符的距離總和，而兩個非空格字符的距離定義為它們的ASCII碼的差的絕對值，而空格字符與其它任意字符之間的距離為已知的定值K，空格字符與空格字符的距離為O。在字符串A、B的所有擴展串中，必定存在兩個等長的擴展串A1、B1，使得A1與B1之間的距離達到最小，我們將這一距離定義為字符串A、B的距離。請你寫一個程序，求出字符串A、B的距離。輸入輸入文件第一行為字符串入，第二行為字符串B，A、B均由小寫字母組成且長度均不超過2000，第三行為一個整數K，1WKW100,表示空格與其它字符的距離。輸出輸出文件僅一行包含一個整數，表示要求的字符串A、B的距離。樣例BLAST.INcmc-3-DPProblemSetnmn2BLAST.OUT10書的復制源程序名BOOK.(PAS,C,CPP)可執(zhí)行文件名BOOK.E某E輸入文件名BOOK.IN輸出文件名BOOK.OUT現在要把M本有順序的書分給K個人復制(抄寫)，每一個人的抄寫速度都一樣，一本書不允許給兩個(或以上)的人抄寫，分給每一個人的書，必須是連續(xù)的，比如不能把第一、第三、第四本數給同一個人抄寫。現在請你設計一種方案，使得復制時間最短。復制時間為抄寫頁數最多的人用去的時間。輸入第一行兩個整數M、K；(K<=M<=100)第二行沖個整數，第i個整數表示第i本書的頁數。輸出123456789BOOK.OUT156789最小乘車費用源程序名BUSSES.(PAS,C,CPP)可執(zhí)行文件名BUSSES.E某E輸入文件名BUSSES.IN輸出文件名BUSSES.OUT-4-DPProblemSet某條街上每一公里就有一汽車站，乘車費用如下表：公里數費用11222133144054965876987999010101而一輛汽車從不行駛超過10公里。某人想行駛n公里，假設他可以任意次換車，請你幫他找到一種乘車方案使費用最小（10公里的費用比1公里小的情況是允許的）。編一程序：從文件BUSSES.IN中讀入對乘車費用的描述；算出最小的價格；把結果寫入文件BUSSES.OUT中。輸入輸入文件共兩行，第一行為10個不超過100的整數，依次表示行駛1?10公里的費用，相鄰兩數間用空格隔開；第二行為某人想要行駛的公里數。輸出輸出文件僅一行包含一個整數，表示該測試點的最小費用。樣例BUSSES.IN12213140495869799010115BUSSES.OUT147筷子源程序名CHOP.(PAS,C,CPP)可執(zhí)行文件名CHOP.E某E輸入文件名CHOP.IN輸出文件名CHOP.OUTA先生有很多雙筷子。確切的說應該是很多根，因為筷子的長度不一，很難判斷出哪兩根是一雙的。這天，A先生家里來了K個客人，A先生留下他們吃晚飯。加上A先生，A夫人和他們的孩子小A，共K+3個人。每人需要用一雙筷子。A先生只好清理了一下筷子，共N根，長度為T1,T2,T3,,TN.現在他想用這些筷子組合成K+3雙，使每雙的筷子長度差的平方和最小。(怎么不是和最小？？這要去問A先生了，呵呵)輸入輸入文件共有兩行，第一行為兩個用空格隔開的整數，表示N,K(1WNW100,0-5-DPProblemSet輸出輸出文件僅一行。如果湊不齊K+3雙，輸出-1,否則輸出長度差平方和的最小值。樣例CHOP.IN101112333461020CHOP.OUT5說明第一雙11第二雙23第三雙33第四雙46(1-1)人2+(2-3)人2+(3-3)人2+(4-6)”=5護衛(wèi)隊源程序名CONVOY.（PAS,C,CPP）可執(zhí)行文件名CONVOY.E某E輸入文件名CONVOY.IN輸出文件名CONVOY.OUT輸入文件第一行包含三個正整數（用空格隔開），第一個整數表示該橋所能承受的最大載重量（用噸表示）；第二個整數表示該橋的長度（用千米表示）；第三個整數表示該護衛(wèi)隊中車輛的總數（n<1000）。接下來的幾行中，每行包含兩個正整數W和S（用空格隔開），W表示該車的重量（用噸表示），S表示該車過橋能達到的最快速度（用千米/小時表示）。車子的重量和速度是按車子排隊等候時的順序給出的。輸出輸出文件應該是一個實數，四舍五入精確到小數點后1位，表示整個護衛(wèi)車隊通過該-6-DPProblemSet橋所需的最短時間（用分鐘表示）。樣例CONVOY.IN100510402550205020701012509704930382527501970CONVOY.OUT75.0DOLLARS源程序名DOLLARS.（PAS,C,CPP）可執(zhí)行文件名DOLLARS.E某E輸入文件名DOLLARS.IN輸出文件名DOLLARS.OUT在以后的若干天里戴維將學習美元與德國馬克的匯率。編寫程序幫助戴維何時應買或賣馬克或美元，使他從100美元開始，最后能獲得最高可能的價值。輸入輸入文件的第一行是一個自然數N,1WNW100,表示戴維學習匯率的天數。接下來的N行中每行是一個自然數A,1WAW1000。第i+1行的A表示預先知道的第i+1天的平均匯率，在這一天中，戴維既能用100美元買A馬克也能用A馬克購買100美元。輸出輸出文件的第一行也是唯一的一行應輸出要求的錢數（單位為美元，保留兩位小數）。注意：考慮到實數算術運算中進位的誤差，結果在正確結果0.05美元范圍內的被認為是正確的，戴維必須在最后一天結束之前將他的錢都換成美元。樣例DOLLARS.IN5400-7-DPProblemSet300500300250DOLLARS.OUT266.66樣例解釋（無需輸出）Day1...changing100.0000美元二400.0000馬克Day2...changing400.0000馬克二133.3333美元Day3...changing133.3333美元二666.6666馬克Day5...changing666.6666馬克二266.6666美元動態(tài)規(guī)劃部分（初中組不作要求）潛水員（ga.e某e）潛水員為了潛水要使用特殊的裝備。他有一個帶2種氣體的氣缸：一個為氧氣，一個為氮氣。讓潛水員下潛的深度需要各種的數量的氧和氮。潛水員有一定數量的氣缸。每個氣缸都有重量和氣體容量。潛水員為了完成他的工作需要特定數量的氧和氮。他完成工作所需氣缸的總重的最低限度的是多少？例如：潛水員有5個氣缸。每行三個數字為：氧，氮的（升）量和氣缸的重量：3361201025129550250145130420119如果潛水員需要5升的氧和60升的氮則總重最小為249（1，2或者4，5號氣缸）。你的任務就是計算潛水員為了完成他的工作需要的氣缸的重量的最低值。輸入格式從文本文件ga.in中讀入數據。第一行有2整數t,a(1<=t<=21,1<=a<=79)。它們表示氧，氮各自需要的量。-8-DPProblemSet第二行為整數n(1<=n<=1000)表示氣缸的個數。此后的n行，每行包括ti，ai，wi(1〈=ti<=21，1〈二ai<=79,1<=wi<=800)3整數。這些各自是：第i個氣缸里的氧和氮的容量及汽缸重量。輸出格式僅一行包含一個整數，為潛水員完成工作所需的氣缸的重量總和的最低值。樣例輸入56053361201025129550250145130420119樣例輸出249饑餓的奶牛(hunger.e某e)John當然不想讓奶牛都餓肚子，所以他希望根據奶牛們提出的請求，滿足其中一些組的要求，使得最多的食桶被奶牛食用。這個難題困擾著John，他希望得到你的幫助。輸入格式從文本文件hunger.in中讀入數據。第一行一個整數n,表示奶牛的組數°（1<=n<=1000）第2~n+1行，每行兩個整數tart和end，描述了一組奶牛提出的請求。輸出格式一個整數，表示最多有多少個食桶可以被食用。樣例輸入-9-DPProblemSet3137834樣例輸出5（滿足第1組和第2組奶牛的要求，這樣1~3號和7~8號這5個食桶可以被食用）單詞的劃分（word.e某e）有一個很長的由小寫字母組成字符串。為了便于對這個字符串進行分析，需要將它劃分成若干個部分，每個部分稱為一個單詞。出于減少分析量的目的，我們希望劃分出的單詞數越少越好。你就是來完成這一劃分工作的。輸入格式從文本文件word.in中讀入數據。第一行，一個字符串。（字符串的長度不超過100）第二行一個整數n，表示單詞的個數°（n<=100）第3~n+2行，每行列出一個單詞。輸出格式一個整數，表示字符串可以被劃分成的最少的單詞數。樣例輸入realityour5realrealityityourour樣例輸出2（原字符串可拆成real+it+your或reality+our，由于reality+our僅為兩個部分，因此最優(yōu)解為2,另外注意，單詞列表中的每個單詞都可以重復使用多次，也可以不用）火車票-10-DPProblemSet（railway.e某e）從Ekaterinburg到Sverdlovk的火車線路上有若干個站點。這條線路可以近似的表示為一條線段，火車站就是線段上的點。線路始于Ekaterinburg，終于Sverdlovk。Ekaterinburg被標號為1，Sverdlovk被標號為n°（n為整條線路上的站點數）線路上的任意兩個站點間的直達票價是由它們間的距離決定的，票價根據以下規(guī)則制定：某為兩站的距離價格0如果兩站的間距超過L3，則無直達車票。所以有時可能有必要買多張票，通過轉車的方式，從一個站到達另一個站。例如，在上面的圖中，有7個站點。2號站點到6號站點的距離超過L3，不能買直達票。存在若干種中轉的方法，其中的一種是買兩張票：先花費C2從2號站到達3號站，然后花費C3從3號站到6號站，一種花費C2+C3。你的任務是，找出一種最經濟的中轉方案。輸入格式從文本文件railway.in中讀入數據。第一行6個整數L1,L2,L3,C1,C2,C3(1<=L1任意兩個車站的距離不超過10"9，任意兩個相鄰的車站的距離不超過L3。輸出格式一個整數，表示從給定的一個站到給定的另一個站的最小花費。樣例輸入368203040726-11-DPProblemSet378131523樣例輸出70加油問題(oil.e某e)一個美國旅行代理上經常被要求去估計開車從一個城市旅行至另一個城市的最小費用。他有一個在通常路線上的大多數加油站的列表。列表包括了所有加油站的位置及當前每加侖汽油的價格。為了簡化估計費用的過程，代理商使用了以下的簡化汽車駕駛員行為的規(guī)則：?除非汽車無法用油箱里的汽油達到下一個加油站（如果有的話）或目的地，在油箱里還有不少于最大容量一半的汽油時，駕駛員從不在加油站停下來。?在每一個停下的加油站，駕駛員總是將油加滿。?在一個加油站停下之后，駕駛員將為旅程在快餐和糖果上花去2.00元。?在駛向加油站或目的地時，駕駛員不需要超過必須量的汽油。不需要“安全余量”。?駕駛員開始旅行時油箱總是滿的?每個加油站付款時四舍五入到分（1元等于100分）。你必須寫一個程序以估計駕駛員在旅程上至少要為汽油和食品付多少錢。輸入格式從文本文件oil.in中讀入數據。開始的2行給出了出發(fā)地和目的地的信息。數據項的后繼行代表了路線上的加油站，每個加油站用一行表示。下面是輸入數據中數據項的精確格式及其含義。第一行：一個實數一一從出發(fā)地到目的地的距離（英里）第二行：三個實數及一個整數?第一個實數是汽車油箱的最大的容量（加侖）?第二個實數是汽車每加侖汽油可以行駛的英里數?第三個實數是汽車在出發(fā)地城市加滿油箱的費用（單位：元）?整數（小于51）是路線上加油站的數目接下來的每一行：兩個實數?第一個實數是從出發(fā)地到加油站的距離（單位：英里）?第二個實數是該加油站出售的汽油每加侖的價格（單位：分）-12-DPProblemSet數據項中的所有數據都是正的。一條路線上的加油站根據其到出發(fā)地的距離遞增排列。路線上不存在這樣的加油站，它到出發(fā)點的距離大于從出發(fā)點到目的地的距離。每條路線上的加油站都被適當的安排以使得任何汽車都能從出發(fā)地開到目的地。輸出格式僅一行，一個實數（保留兩位小數），表示最小的花費（單位：元）。樣例輸入475.611.927.414.986102.099.9220.0132.9256.3147.9275.0102.9277.6112.9381.8100.9樣例輸出27.31公路乘車（bue.e某e）一個特別的單行街道在每公里處有一個汽車站。顧客根據他們乘坐汽車的公里使來付費。例如下表就是一個費用的單子。沒有一輛車子行駛超過10公里，一個顧客打算行駛n公里（1〈二n<=100），它可以通過無限次的換車來完成旅程。最后要求費用最少。輸入格式第一行十個整數分別表示行走1到10公里的費用（<=500）。注意這些數并無實際的經濟意義，即行駛10公里費用可能比行駛一公里少。第二行一個整數n表示，旅客的總路程數。輸出格式僅一個整數表示最少費用。樣例輸入12213140495869799010115-13-DPP