DP练习试题解读Word格式文档下载.docx

1、=50 ）。下面n行每行有一对数，分别为 Ti和Fi，均为不大于100的正整数，表示第i个任务单独完成所需的时间是 Ti及其费 用系数Fi。一个数，最小的总费用。5113324323141533.最大的算式（bigexp）题目很简单，给出 N个数字，不改变它们的相对位置，在中间加入 K个乘号和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输入文件共有二行，第一行为两

2、个有空格隔开的整数，表示 N和K，其中（2=N=15, 0=K=N-1 ）。第二行为 N个用空格隔开的数字（每个数字在 0到9之间）。输出文件仅一行包含一个整数，表示要求的最大的结果5212 3 4 5120Hint【样例说明】：（1+2+3）*4*5=1204.字符串距离（blast）【问题描述】设有字符串X，我们称在X的头尾及中间插入任意多个空格后构成的新字符串为 X的扩展串，如字符串X为“abcbcd”则字符串“abcbDcd” 口aDbcbcd和” “abcbDcd”是X的扩展串，这里 代表空格字符。如果A1是字符串A的扩展串，B1是字符串B的扩展串，A1与B1具有相同的长度，那么我们

3、定义字符串 A1与B1的距离为相应位置上的字符的距离总和，而两个非空格字符的距离定义为它们的 ASCII码的差的绝对值，而空格字符与其它任意字符之间的距离为已知的定值 K，空格字符与空格字符的距离为 0。在字符串A、B的所有扩展串中，必定存在两个等长的扩展串A1、B1，使得A1与B1之间的距离达到最小，我们将这一距离定义为字符串 A、B的距离。请你写一个程序，求岀字符串 A、B的距离。【输入文件】输入文件第一行为字符串 A，第二行为字符串B，A、B均由小写字母组成且长度均不超过 2000，第三行为一个整数 K，K K 10,0表示空格与其它字符的距离。【输岀文件】输岀文件仅一行包含一个整数，表

4、示要求的字符串 A、B的距离。【输入输出样例】输入：cmcsnmn2输出：105.书的复制（Book）现在要把M本有顺序的书分给 K个人复制（抄写），每一个人的抄写速度都一样，一本书不允许给两个（或以上）的 人抄写，分给每一个人的书，必须是连续的，比如不能把第一、第三、第四本数给同一个人抄写。现在请你设计一种方案， 使得复制时间最短。复制时间为抄写页数最多的人用去的时间。第一行两个整数 M、K ；（ Kv=M=100）第二行M个整数，第i个整数表示第i本书的页数。共K行，每行两个正整数，第i行表示第i个人抄写的书的起始编号和终止编号。 K行的起始编号应该从小到大排列,如果有多解，则尽可能让前面

5、的人少抄写。【输入输出样例】 输入：9312 3 4 5 6 7 8 9156789一个特别的单行街道在每公里处有一个汽车站。6.公路乘车（busses顾客根据他们乘坐汽车的公里使来付费。例如下表就是一个费用的单子kilometres2p3#4p7a%12prices12p2131p465869十90101没有一辆车子行驶超过 10公里，一个顾客打算行驶 n公里（1=100），它可以通过无限次的换车来完成旅程。最后要求费用最少。第一行十个整数分别表示行走 1到10公里的费用（=500）。注意这些数并无实际的经济意义，即行驶 10公里费用可能比行驶一公里少。第二行一个整数n表示，旅客的总路程数。

6、仅一个整数表示最少费用。12 21 31 40 49 58 69 79 90 1011477.积木城堡（Castle）XC的儿子小XC最喜欢玩的游戏用积木垒漂亮的城堡。 城堡是用一些立方体的积木垒成的， 城堡的每一层是一块积木。小XC是一个比他爸爸XC还聪明的孩子，他发现垒城堡的时候，如果下面的积木比上面的积木大，那么城堡便不容易倒。 所以他在垒城堡的时候总是遵循这样的规则。小XC想把自己垒的城堡送给幼儿园里漂亮的女孩子们， 这样可以增加他的好感度。 为了公平起见，他决定把送给每个女孩子一样高的城堡，这样可以避免女孩子们为了获得更漂亮的城堡而引起争执。 可是他发现自己在垒城堡的时候并没有预先考

7、虑到这一点。所以他现在要改造城堡。由于他没有多余的积木了，他灵机一动，想岀了一个巧妙的改造方案。他决定从 每一个城堡中挪去一些积木， 使得最终每座城堡都一样高。 为了使他的城堡更雄伟，他觉得应该使最后的城堡都尽可能的高。请你帮助小XC编一个程序，根据他垒的所有城堡的信息，决定应该移去哪些积木才能获得最佳的效果。第一行是一个整数 N （ NV=1OO ），表示一共有几座城堡。以下 N行每行是一系列非负整数，用一个空格分隔，按从下往 上的顺序依次给出一座城堡中所有积木的棱长。用 -1结束。一座城堡中的积木不超过 100块，每块积木的棱长不超过 100一个整数，表示最后城堡的最大可能的高度。如果找不

8、到合适的方案，则输出 0。21 -132 1 -138.筷子（chop）A先生有很多双筷子。确切的说应该是很多根，因为筷子的长度不一，很难判断出哪两根是一双的。这天， A先生家里来了 K个客人，A先生留下他们吃晚饭。加上 A先生，A夫人和他们的孩子小 A，共K+3个人。每人需要用一双筷子。 A先生只好清理了一下筷子，共 N根，长度为T1，T2，T3，TN。现在他想用这些筷子组合成 K+3双，使每双的筷子长度差的平方和最小。（怎么不是和最小？这要去问 A先生了，呵呵）输入文件共有两行，第一行为两个用空格隔开的整数，表示 N，K （ KNC10Q 0K50 ），第二行共有N个用空格隔开的整数，为T

9、I每个整数为1 50之间的数。 font输岀文件仅一行。如果凑不齐 K+3双，输岀-1,否则输岀长度差平方和的最小值。1011 1 2 3 3 3 4 6 10 20第一双1 1第二双2 3第三双3 3第四双4 6（1-1）A2+（2-3）A2+（3-3）A2+（4-6）A2=5护卫车队在一条单行的街道前排成一队， 前面河上是一座单行的桥。因为街道是一条单行道，所以任何车辆都不能超车。桥能承受一个给定的最大承载量。为了控制桥上的交通，桥两边各站一个指挥员。护卫车队被分成几个组，每组中的车辆都 能同时通过该桥。当一组车队到达了桥的另一端， 该端的指挥员就用电话通知另一端的指挥员， 这样下一组车队

10、才能开始通过该桥。每辆车的重量是已知的。任何一组车队的重量之和不能超过桥的最大承重量。 被分在同一组的每一辆车都以其最快的速度通过该桥。一组车队通过该桥的时间是用该车队中速度最慢的车通过该桥所需的时间来表示的。 问题要求计算岀全部护卫车队通过该桥所需的最短时间值。输入文件第一行包含三个正整数（用空格隔开），第一个整数表示该桥所能承受的最大载重量（用吨表示）；第二个整 数表示该桥的长度（用千米表示）；第三个整数表示该护卫队中车辆的总数（ n1000）。接下来的几行中，每行包含两个正整数 W和S （用空格隔开），W表示该车的重量（用吨表示）, S表示该车过桥能达到的最快速度（用千米 /小时表示）。

11、车子的重量和速度是按车子排队等候时的顺序给岀的。输岀文件应该是一个实数，四舍五入精确到小数点后 1位，表示整个护卫车队通过该桥所需的最短时间 （用分钟表示）100 5 1040 2550 2070 1012 5097049 3038 2527 5019 7075.010.对话（dialog）从前有两个人，一个名为 “one”另一个则叫“puton。很奇怪，“one除了称呼“puton名字外，只对他说 “out和“output两个单词；“puton除了称呼“one名字外，只对他说 “in和“input两个单词。最近人们在研究他们对话，但是，由于资料的混乱，其中可能有一些不是他们的对话。你的任务是

12、鉴别一些句子，判断这些句子是否可能是他们的对话。（即，判断句子是否可以被划分成若干单词，这些单词只可以是 “one” “puton、“out、”“output、” “in禾和 “input）输入n个字符串，长度不超过 200,表示一句句子。如果可能是那两个人的对话，则输出 “YES;否则，输出“NO。第一行一个整数n，表示一共有n句句子。此后每行一个字符串，表示一句句子。n行，每行一个“YES或“NO,表示你的判断结果。6putoninonputinoneputonininputoutoutputoneininputwooutoutputoutpuutputYESNO11.DOLLARS（do

13、llars）在以后的若干天里戴维将学习美元与德国马克的汇率。 编写程序帮助戴维何时应买或卖马克或美元， 使他从100美元开始，最后能获得最高可能的价值。输入文件的第一行是一个自然数 N , 1WNK10Q表示戴维学习汇率的天数。接下来的N行中每行是一个自然数 A , 1A1000第i+1行的A表示预先知道的第i+1天的平均汇率，在这一天中， 戴维既能用100美元买A马克也能用A马克购买100美元。输出文件的第一行也是唯一的一行应输出要求的钱数 （单位为美元，保留两位小数）。注意：考虑到实数算术运算中进位的误差，结果在正确结果 0.05美元范围内的被认为是正确的，戴维必须在最后一天结束之前将他的

14、钱都换成美元。400300500250266.66【样例解释】：（无需输岀）=400.0000 马克=133.3333 美元=666.6666 马克=266.6666 美元Day 1 . changing 100.0000 美元Day 2 . changing 400.0000 马克Day 3 . changing 133.3333 美元Day 5 . changing 666.6666 马克12.胖男孩（fatboy）麦克正如我们所知的已快乐地结婚，在上个月他胖了 70磅。因为手指上的脂肪过多，使他连给他最亲密的朋友斯拉夫克写一个电子邮件都很困难。每晚麦克都详细地描述那一天他所吃的所有东西，

15、 但有时当他只想按一次某键时往往会按了不止一次， 并且他的胖手指还会碰到他不想要按的键，麦克也知道自己的手指有问题， 因此他在打字的时候很小心，以确保每打一个想要的字符时误打的字符不超过3个，误打的字符可能在正确字符之前也可能在其之后。当斯拉夫克多次收到读不懂的电子邮件后，他总是要求麦克将电子邮件发 3遍，使他容易读懂一点。编写程序，帮助斯拉夫克根据他所收到的三封电子邮件求岀麦克可能写岀的最长的信。输入文件包含了三行文本。每一行文本包括麦克信件的一种版本。 其中所有的字符都由英文字母表中的小写字母组成并且不超过100个。输岀文件中第一行即唯一的一行数据应该包含斯拉夫克根据所收到的电子邮件推测岀

16、的最长信件。 你可以相信问题一定有解，但解不一定是唯一的。cecqbhvaiaedpibaluk cabegviapcihlaaugck adceevfdadaepcialaukdcevapiluk约翰是个垂钓谜，星期天他决定外岀钓鱼 h小时（1h16，约翰家附近共有 n个池塘（2n25,这些池塘分布在一条直线上，约翰将这些池塘按离家的距离编上号，依次为 L1 , L2 ,，Ln，约翰家门外就是第一个池塘，所以他到第一个池塘是不用花时间的，约翰可以任选若干个池塘垂钓，并且在每个池塘他都可以呆上任意长的时间，但呆的时间必须为 5分钟的倍数，（5分钟为一个单位时间），已知从池塘Li到池塘Li+1要

17、化去约翰ti个单位时间，每个池塘的上鱼率预先也是 已知的，池塘Li在第一个单位时间内能钓到的鱼为 Fi（OWFi 10）,并且每过一个单位时间在单位时间内能钓到的鱼将减少一个常数di （Owdi 10Q现在请你编一个程序计算约翰最多能钓到多少鱼。输入文件第一行为一个整数 n，第二行为一个整数 h，第三行为n个用空格隔开的整数，表示 Fi （i=1，2，n），第 四行为n个用空格隔开的整数，表示 di （i=1，2，n），第五行为n-1个用空格隔开的整数，表示 ti （i=1，2，n-1）输岀一个整数，表示约翰最多能钓到的鱼的数量。253114.文件排版（format）写电子邮件是有趣的，但不幸

18、的是经常写不好看， 主要是因为所有的行不一样长， 你的上司想要发排版精美的电子邮件，你的任务是为他编写一个电子邮件排版程序。完成这个任务最简单的办法是在太短的行中的单词之间插入空格，但这并不是最好的方法，考虑如下例子：*This is the example you areactually considering.假设我们想将第二行变得和第一行一样长，靠简单地插入空格则我们将得到如下结果：但这太难看了，因为在第二行中有一个非常大的空白，如果将第一行的单词 “are移到下一行我们将得到较好的结果：This is the example youare actually considering.当然

19、，这必须对难看程度进行量化。因此我们必须给出单词之间的空格的难看程度，一个包含 N个空格符的空白段，其难看程度值为（n-1）2，程序的目的是使难看程度的总和最小化。例如，第一个例子的难看程度是 1+7*7=50，而第二个例子的难看程度仅为 1+1+1+4+1+4=12。输出时，每一行的开头和结尾处都必须是一个单词， 即每行开头和结尾处不能有空白。 唯一例外的是该行仅有一个单词组成的情况，对于这种情况你可将单词放在该行开头处输岀， 此时如果该单词比该行应有的长度短则我们指定它的最坏程度为500，当然在这种情况下，该行的实际长度即为该单词的长度。输入文件第一行是一个整数 N，表示该段要求达到的宽度

20、，1=80。该段文章由一个或多个单词组成， 单词由ASCII码值为33到126 （包含33和126）的字符组成，单词与单词之间用空格隔开（可能超过一个）。单词长度不会超过段落要 求达到的宽度。一段文字所有单词的总长度不会超过 10000个字符，任何一行都不会超过100个字符，任何一个单词都在同一行内。对于每个段落，找出使其难看程度最小的排版形式并输出句子： “Minimal badness is B.，B是指按可能的最好排版形式会发生的难看程度值。注意排版后文本行数任意，多余的空格也可删除。28Minimal badness is 12.潜水员为了潜水要使用特殊的装备。 他有一个带2种气体的气

21、缸：一个为氧气，一个为氮气。 让潜水员下潜的深度需要各种的数量的氧和氮。 潜水员有一定数量的气缸。 每个气缸都有重量和气体容量。 潜水员为了完成他的工作需要特定数量的氧和氮。他完成工作所需气缸的总重的最低限度的是多少？潜水员有5个气缸。每行三个数字为：氧，氮的（升）量和气缸的重量：336 12010 25 129550 2501 45 130420 119如果潜水员需要5升的氧和60升的氮则总重最小为 249（ 1，2或者4，5号气缸）。你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的最低值。从文本文件gas.in中读入数据。第一行有2整数t，a（ 1=t=21，1=a=79 ）。它们

22、表示氧，氮各自需要的量。第二行为整数n （1=1000）表示气缸的个数。此后的n行，每行包括ti，ai，wi （ 1=ti=21， 1=ai=79， 1=wi=800）3整数。这些各自是：第 i个气缸里的氧和 氮的容量及汽缸重量。仅一行包含一个整数，为潜水员完成工作所需的气缸的重量总和的最低值。5 605 50 25024916.相似基因（Gene）大家都知道，基因可以看作一个碱基对序列。它包含了 4种核苷酸，简记作 A，C，G，T。生物学家正致力于寻找人类基因的功能，以利用于诊断疾病和发明药物。在一个人类基因工作组的任务中，生物学家研究的是：两个基因的相似程度。因为这个研究对疾病的治疗有着非

23、同寻 常的作用。两个基因的相似度的计算方法如下：AGT-对于两个已知基因，例如 AGTGATG和GTTAG，将它们的碱基互相对应。当然，中间可以加入一些空碱基 -，例如:这样，两个基因之间的相似度就可以用碱基之间相似度的总和来描述，碱基之间的相似度如下表所示:C-1-2-3-4*那么相似度就是：（-3）+5+5+（-2）+（-3）+5+（-3）+5=9。因为两个基因的对应方法不唯一，例如又有:相似度为：（-3）+5+5+（-2）+5+（-1）+5=14。规定两个基因的相似度为所有对应方法中，相似度最大的那个。共两行。每行首先是一个整数，表示基因的长度；隔一个空格后是一个基因序列，序列中只含 A

24、，C，G，T四个字母1=序列的长度=100。仅一行，即输入基因的相似度。7AGTGATG5 GTTAG输岀：仃.饥饿的奶牛（hunger）John养了若干奶牛，每天晚上奶牛都要进食。由于条件比较简陋，并不一定所有奶牛都能吃到食物。奶牛的进食方式 是这样的：John有n个食桶（1=2000），分别编号为1.n。这些食桶被按照编号排成一行。 John将奶牛们分成若干组,每组奶牛总是呆在一起进食的，每组奶牛会提岀要求 他们需要吃第start到第end桶中的食物。可能存在若干组奶牛都要吃同一个桶中的食物，从而就产生了冲突，这时 John只能满足其中一组的要求，另一些组就只能饿肚子了。John当然不想让奶牛都饿肚子，所以他希望根据奶牛们提出的请求，满足其中一些组的要求，使得最多的