DP练习试题解读Word格式文档下载.docx
《DP练习试题解读Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《DP练习试题解读Word格式文档下载.docx（37页珍藏版）》请在冰点文库上搜索。
=50）。
下面n行每行有一对数，分别为Ti和Fi，均为不大于100的正整数，表示第i个任务单独完成所需的时间是Ti及其费用系数Fi。
一个数，最小的总费用。
5
1
13
32
43
23
14
153
3.最大的算式（bigexp）
题目很简单，给出N个数字，不改变它们的相对位置，在中间加入K个乘号和N-K-1个加号，（括号随便加）使最终
结果尽量大。
因为乘号和加号一共就是N-1个了，所以恰好每两个相邻数字之间都有一个符号。
N=5，K=2，5个数字分别为1、2、3、4、5,可以加成：
1*2*（3+4+5）=24
1*（2+3）*（4+5）=45
（1*2+3）*（4+5）=45
输入文件共有二行，第一行为两个有空格隔开的整数，表示N和K，其中（2<
=N<
=15,0<
=K<
=N-1）。
第二行为N个
用空格隔开的数字（每个数字在0到9之间）。
输出文件仅一行包含一个整数，表示要求的最大的结果
52
12345
120
Hint
【样例说明】：
（1+2+3）*4*5=120
4.字符串距离（blast）
【问题描述】
设有字符串X，我们称在X的头尾及中间插入任意多个空格后构成的新字符串为X的扩展串，如字符串X为“abcbcd”
则字符串“abcbDcd”"
口aDbcbcd和”“abcbDcd□”是X的扩展串，这里"
□代表空格字符。
如果A1是字符串A的扩展串，B1是字符串B的扩展串，A1与B1具有相同的长度，那么我们定义字符串A1与B1的距
离为相应位置上的字符的距离总和，而两个非空格字符的距离定义为它们的ASCII码的差的绝对值，而空格字符与其它任
意字符之间的距离为已知的定值K，空格字符与空格字符的距离为0。
在字符串A、B的所有扩展串中，必定存在两个等长
的扩展串A1、B1，使得A1与B1之间的距离达到最小，我们将这一距离定义为字符串A、B的距离。
请你写一个程序，求岀字符串A、B的距离。
【输入文件】
输入文件第一行为字符串A，第二行为字符串B，A、B均由小写字母组成且长度均不超过2000，第三行为一个整数K，
KK<
10,0表示空格与其它字符的距离。
【输岀文件】
输岀文件仅一行包含一个整数，表示要求的字符串A、B的距离。
【输入输出样例】
输入：
cmc
snmn
2
输出：
10
5.书的复制（Book）
现在要把M本有顺序的书分给K个人复制（抄写），每一个人的抄写速度都一样，一本书不允许给两个（或以上）的人抄写，分给每一个人的书，必须是连续的，比如不能把第一、第三、第四本数给同一个人抄写。
现在请你设计一种方案，使得复制时间最短。
复制时间为抄写页数最多的人用去的时间。
第一行两个整数M、K；
（Kv=M<
=100）
第二行M个整数，第i个整数表示第i本书的页数。
共K行，每行两个正整数，第i行表示第i个人抄写的书的起始编号和终止编号。
K行的起始编号应该从小到大排列,
如果有多解，则尽可能让前面的人少抄写。
【输入输出样例】输入：
93
123456789
15
67
89
一个特别的单行街道在每公里处有一个汽车站。
6.公路乘车（busses
顾客根据他们乘坐汽车的公里使来付费。
例如下表就是一个费用的单子
kilometres
2p
3#
4p
7a
%
12
prices
12p
21^
31p
46
58^
69十
90
101^
没有一辆车子行驶超过10公里，一个顾客打算行驶n公里（1<
=100），它可以通过无限次的换车来完成旅程。
最
后要求费用最少。
第一行十个整数分别表示行走1到10公里的费用（<
=500）。
注意这些数并无实际的经济意义，即行驶10公里费用可
能比行驶一公里少。
第二行一个整数n表示，旅客的总路程数。
仅一个整数表示最少费用。
122131404958697990101
147
7.积木城堡（Castle）
XC的儿子小XC最喜欢玩的游戏用积木垒漂亮的城堡。
城堡是用一些立方体的积木垒成的，城堡的每一层是一块积木。
小XC是一个比他爸爸XC还聪明的孩子，他发现垒城堡的时候，如果下面的积木比上面的积木大，那么城堡便不容易倒。
所以他在垒城堡的时候总是遵循这样的规则。
小XC想把自己垒的城堡送给幼儿园里漂亮的女孩子们，这样可以增加他的好感度。
为了公平起见，他决定把送给每个
女孩子一样高的城堡，这样可以避免女孩子们为了获得更漂亮的城堡而引起争执。
可是他发现自己在垒城堡的时候并没有预
先考虑到这一点。
所以他现在要改造城堡。
由于他没有多余的积木了，他灵机一动，想岀了一个巧妙的改造方案。
他决定从每一个城堡中挪去一些积木，使得最终每座城堡都一样高。
为了使他的城堡更雄伟，他觉得应该使最后的城堡都尽可能的高。
请你帮助小XC编一个程序，根据他垒的所有城堡的信息，决定应该移去哪些积木才能获得最佳的效果。
第一行是一个整数N（NV=1OO），表示一共有几座城堡。
以下N行每行是一系列非负整数，用一个空格分隔，按从下往上的顺序依次给出一座城堡中所有积木的棱长。
用-1结束。
一座城堡中的积木不超过100块，每块积木的棱长不超过100
一个整数，表示最后城堡的最大可能的高度。
如果找不到合适的方案，则输出0。
21-1
321-1
3
8.筷子（chop）
A先生有很多双筷子。
确切的说应该是很多根，因为筷子的长度不一，很难判断出哪两根是一双的。
这天，A先生家里
来了K个客人，A先生留下他们吃晚饭。
加上A先生，A夫人和他们的孩子小A，共K+3个人。
每人需要用一双筷子。
A
先生只好清理了一下筷子，共N根，长度为T1，T2，T3，……，TN。
现在他想用这些筷子组合成K+3双，使每双的筷子
长度差的平方和最小。
（怎么不是和最小？
？
这要去问A先生了，呵呵）
输入文件共有两行，第一行为两个用空格隔开的整数，表示N，K（KNC10Q0<
K<
50），第二行共有N个用空格隔
开的整数，为TI每个整数为1~50之间的数。
<
font〉
输岀文件仅一行。
如果凑不齐K+3双，输岀-1,否则输岀长度差平方和的最小值。
101
112333461020
第一双11
第二双23
第三双33
第四双46
（1-1）A2+（2-3）A2+（3-3）A2+（4-6）A2=5
护卫车队在一条单行的街道前排成一队，前面河上是一座单行的桥。
因为街道是一条单行道，所以任何车辆都不能超车。
桥能承受一个给定的最大承载量。
为了控制桥上的交通，桥两边各站一个指挥员。
护卫车队被分成几个组，每组中的车辆都能同时通过该桥。
当一组车队到达了桥的另一端，该端的指挥员就用电话通知另一端的指挥员，这样下一组车队才能开始通
过该桥。
每辆车的重量是已知的。
任何一组车队的重量之和不能超过桥的最大承重量。
被分在同一组的每一辆车都以其最快
的速度通过该桥。
一组车队通过该桥的时间是用该车队中速度最慢的车通过该桥所需的时间来表示的。
问题要求计算岀全部
护卫车队通过该桥所需的最短时间值。
输入文件第一行包含三个正整数（用空格隔开），第一个整数表示该桥所能承受的最大载重量（用吨表示）；
第二个整数表示该桥的长度（用千米表示）；
第三个整数表示该护卫队中车辆的总数（n<
1000）。
接下来的几行中，每行包含两个
正整数W和S（用空格隔开），W表示该车的重量（用吨表示）,S表示该车过桥能达到的最快速度（用千米/小时表示）。
车子的重量和速度是按车子排队等候时的顺序给岀的。
输岀文件应该是一个实数，四舍五入精确到小数点后1位，表示整个护卫车队通过该桥所需的最短时间（用分钟表示）
100510
4025
5020
7010
1250
970
4930
3825
2750
1970
75.0
10.对话（dialog）
从前有两个人，一个名为“one”另一个则叫“puton。
很奇怪，“one除了称呼“puton名字外，只对他说“out和“output
两个单词；
“puton除了称呼“one名字外，只对他说“in和“input两个单词。
最近人们在研究他们对话，但是，由于资料的混乱，其中可能有一些不是他们的对话。
你的任务是鉴别一些句子，判断
这些句子是否可能是他们的对话。
（即，判断句子是否可以被划分成若干单词，这些单词只可以是“one”“puton、“out、”
“output、”“in禾和“input）
输入n个字符串，长度不超过200,表示一句句子。
如果可能是那两个人的对话，则输出“YES;
否则，输出“NO。
第一行一个整数n，表示一共有n句句子。
此后每行一个字符串，表示一句句子。
n行，每行一个“YES或“NO,表示你的判断结果。
6
puton
inonputin
oneputonininputoutoutput
oneininputwooutoutput
outpu
utput
YES
NO
11.DOLLARS（dollars）
在以后的若干天里戴维将学习美元与德国马克的汇率。
编写程序帮助戴维何时应买或卖马克或美元，使他从100美元开
始，最后能获得最高可能的价值。
输入文件的第一行是一个自然数N,1WNK10Q表示戴维学习汇率的天数。
接下来的N行中每行是一个自然数A,1<
A<
1000第i+1行的A表示预先知道的第i+1天的平均汇率，在这一天中，戴维既能用100美元买A马克也能用A马克购买100美元。
输出文件的第一行也是唯一的一行应输出要求的钱数（单位为美元，保留两位小数）。
注意：
考虑到实数算术运算中进位的误差，结果在正确结果0.05美元范围内的被认为是正确的，戴维必须在最后一天
结束之前将他的钱都换成美元。
400
300
500
250
266.66
【样例解释】：
（无需输岀）
=400.0000马克
=133.3333美元
=666.6666马克
=266.6666美元
Day1...changing100.0000美元
Day2...changing400.0000马克
Day3...changing133.3333美元
Day5...changing666.6666马克
12.胖男孩（fatboy）
麦克正如我们所知的已快乐地结婚，在上个月他胖了70磅。
因为手指上的脂肪过多，使他连给他最亲密的朋友斯拉夫
克写一个电子邮件都很困难。
每晚麦克都详细地描述那一天他所吃的所有东西，但有时当他只想按一次某键时往往会按了不止一次，并且他的胖手指
还会碰到他不想要按的键，麦克也知道自己的手指有问题，因此他在打字的时候很小心，以确保每打一个想要的字符时误打
的字符不超过3个，误打的字符可能在正确字符之前也可能在其之后。
当斯拉夫克多次收到读不懂的电子邮件后，他总是要求麦克将电子邮件发3遍，使他容易读懂一点。
编写程序，帮助斯拉夫克根据他所收到的三封电子邮件求岀麦克可能写岀的最长的信。
输入文件包含了三行文本。
每一行文本包括麦克信件的一种版本。
其中所有的字符都由英文字母表中的小写字母组成并
且不超过100个。
输岀文件中第一行即唯一的一行数据应该包含斯拉夫克根据所收到的电子邮件推测岀的最长信件。
你可以相信问题一定
有解，但解不一定是唯一的。
cecqbhvaiaedpibalukcabegviapcihlaaugckadceevfdadaepcialaukd
cevapiluk
约翰是个垂钓谜，星期天他决定外岀钓鱼h小时（1<
h<
16，约翰家附近共有n个池塘（2<
n<
25,这些池塘分布在一
条直线上，约翰将这些池塘按离家的距离编上号，依次为L1,L2,…，Ln，约翰家门外就是第一个池塘，所以他到第一个
池塘是不用花时间的，约翰可以任选若干个池塘垂钓，并且在每个池塘他都可以呆上任意长的时间，但呆的时间必须为5
分钟的倍数，（5分钟为一个单位时间），已知从池塘Li到池塘Li+1要化去约翰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）
输岀一个整数，表示约翰最多能钓到的鱼的数量。
25
31
14.文件排版（format）
写电子邮件是有趣的，但不幸的是经常写不好看，主要是因为所有的行不一样长，你的上司想要发排版精美的电子邮件，
你的任务是为他编写一个电子邮件排版程序。
完成这个任务最简单的办法是在太短的行中的单词之间插入空格，但这并不是最好的方法，考虑如下例子：
****************************
Thisistheexampleyouare
actuallyconsidering.
假设我们想将第二行变得和第一行一样长，靠简单地插入空格则我们将得到如下结果：
但这太难看了，因为在第二行中有一个非常大的空白，如果将第一行的单词“are移到下一行我们将得到较好的结果：
Thisistheexampleyou
areactuallyconsidering.
当然，这必须对难看程度进行量化。
因此我们必须给出单词之间的空格的难看程度，一个包含N个空格符的空白段，
其难看程度值为（n-1）2，程序的目的是使难看程度的总和最小化。
例如，第一个例子的难看程度是1+7*7=50，而第二个例子
的难看程度仅为1+1+1+4+1+4=12。
输出时，每一行的开头和结尾处都必须是一个单词，即每行开头和结尾处不能有空白。
唯一例外的是该行仅有一个单词
组成的情况，对于这种情况你可将单词放在该行开头处输岀，此时如果该单词比该行应有的长度短则我们指定它的最坏程度
为500，当然在这种情况下，该行的实际长度即为该单词的长度。
输入文件第一行是一个整数N，表示该段要求达到的宽度，1<
=80。
该段文章由一个或多个单词组成，单词由ASCII
码值为33到126（包含33和126）的字符组成，单词与单词之间用空格隔开（可能超过一个）。
单词长度不会超过段落要求达到的宽度。
一段文字所有单词的总长度不会超过10000个字符，任何一行都不会超过100个字符，任何一个单词都在同
一行内。
对于每个段落，找出使其难看程度最小的排版形式并输出句子：
“MinimalbadnessisB.，B是指按可能的最好排版形式
会发生的难看程度值。
注意排版后文本行数任意，多余的空格也可删除。
28
Minimalbadnessis12.
潜水员为了潜水要使用特殊的装备。
他有一个带2种气体的气缸：
一个为氧气，一个为氮气。
让潜水员下潜的深度需要
各种的数量的氧和氮。
潜水员有一定数量的气缸。
每个气缸都有重量和气体容量。
潜水员为了完成他的工作需要特定数量的
氧和氮。
他完成工作所需气缸的总重的最低限度的是多少？
潜水员有5个气缸。
每行三个数字为：
氧，氮的（升）量和气缸的重量：
336120
1025129
550250
145130
420119
如果潜水员需要5升的氧和60升的氮则总重最小为249（1，2或者4，5号气缸）。
你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的最低值。
从文本文件gas.in中读入数据。
第一行有2整数t，a（1<
=t<
=21，1<
=a<
=79）。
它们表示氧，氮各自需要的量。
第二行为整数n（1<
=1000）表示气缸的个数。
此后的n行，每行包括ti，ai，wi（1<
=ti<
=21，1<
=ai<
=79，1<
=wi<
=800）3整数。
这些各自是：
第i个气缸里的氧和氮的容量及汽缸重量。
仅一行包含一个整数，为潜水员完成工作所需的气缸的重量总和的最低值。
560
550250
249
16.相似基因（Gene）
大家都知道，基因可以看作一个碱基对序列。
它包含了4种核苷酸，简记作A，C，G，T。
生物学家正致力于寻找人类
基因的功能，以利用于诊断疾病和发明药物。
在一个人类基因工作组的任务中，生物学家研究的是：
两个基因的相似程度。
因为这个研究对疾病的治疗有着非同寻常的作用。
两个基因的相似度的计算方法如下：
A
G
T
-
对于两个已知基因，例如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，C，G，T四个字母
1<
=序列的长度<
=100。
仅一行，即输入基因的相似度。
7AGTGATG
5GTTAG
输岀：
仃.饥饿的奶牛（hunger）
John养了若干奶牛，每天晚上奶牛都要进食。
由于条件比较简陋，并不一定所有奶牛都能吃到食物。
奶牛的进食方式是这样的：
John有n个食桶（1<
=2000），分别编号为1..n。
这些食桶被按照编号排成一行。
John将奶牛们分成若干组,
每组奶牛总是呆在一起进食的，每组奶牛会提岀要求他们需要吃第start到第end桶中的食物。
可能存在若干组奶牛都
要吃同一个桶中的食物，从而就产生了冲突，这时John只能满足其中一组的要求，另一些组就只能饿肚子了。
John当然不想让奶牛都饿肚子，所以他希望根据奶牛们提出的请求，满足其中一些组的要求，使得最多的
升级会员 