动态规划NOIP的题目

《动态规划NOIP的题目》由会员分享，可在线阅读，更多相关《动态规划NOIP的题目（20页珍藏版）》请在金锄头文库上搜索。

1、动态规划 NOIP 的题目DPProblemSet顺序对齐源程序名ALIGN.(PAS,C,CPP)可执行文件名ALIGN.E某E输入文件名 ALIGN.IN 输出文件名 ALIGN.OUT考虑两个字符串右对齐的最佳解法。例如，有一个右对齐方案中字符 串是 AADDEFGGHC 和 ADCDEGH。AAD_DEFGGHCADCDE_GH_每一个数值匹配的位置值2分，一段连续的空格值-1 分。所以总分 是匹配点的2 倍减去连续空格的段数，在上述给定的例子中，6个位置 (A,D,D,E,G,H)匹配，三段空格，所以得分2某6+(-1)某3=9，注意，我 们并不处罚左边的不匹配位置。若匹配的位置是两

2、个不同的字符，则既不 得分也不失分。请你写个程序找出最佳右对齐方案。输入输入文件包含两行，每行一个字符串，最长50个字符。字符全部是 大字字母。输出一行，为最佳对齐的得分。样例 ALIGN.INAADDEFGGHCADCDEGHALIGN.OUT9任务安排源程序名BATCH.（PAS,C,CPP）可执行文件名BATCH.E某E输入文件名BATCH.IN 输出文件名 BATCH.OUTN 个任务排成一个序列在一台机器上等待完成（顺序不得改变），这N 个任务被分成若干批，每批包含相邻的若干任务。从时刻0 开始，这些 任务被分批加工，第i个任务单独完成所需的时间是Ti。在每批任务开 始前，机器需要启

3、动时间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及其费用系数F

4、i。输出一个数，最小的总费用。样例 BATCH.IN511332432314BATCH.OUT153最大的算式源程序名BIGE某P.(PAS,C,CPP)可执行文件名BIGE某P.E某E输入 文件名 BIGE 某 P.IN 输出文件名 BIGE 某 P.OUT题目很简单，给出 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、+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)可执行文件名BLAST.E某E输入文件名 BLAST.IN 输出文件名 BLAST.OUT设有字符串某，我们称在某的头尾及中间插入任意多

6、个空格后构成的 新字符串为某的扩展串，如字符串某为“abcbcd”，则字符串“abcbcd”，“DaDbcbcd口 ”和“abcbcd口 ”都是某的扩展串，这 里“”代表空格字符。如果A1是字符串A的扩展串，B1是字符串B的扩展串，A1与B1具 有相同的长度，那么我们定义字符串 A1 与 B1 的距离为相应位置上的字符 的距离总和，而两个非空格字符的距离定义为它们的 ASCII 码的差的绝对 值，而空格字符与其它任意字符之间的距离为已知的定值K，空格字符与 空格字符的距离为0。在字符串A、B的所有扩展串中，必定存在两个等 长的扩展串Al、B1,使得A1与B1之间的距离达到最小，我们将这一距 离

7、定义为字符串A、B的距离。请你写一个程序，求出字符串A、B的距离。输入输入文件第一行为字符串A，第二行为字符串B，A、B均由小写字母 组成且长度均不超过2000，第三行为一个整数K，1WKW100，表示空格 与其它字符的距离。输出输出文件仅一行包含一个整数，表示要求的字符串A、B的距离。样 例 BLAST.INcmcDPProblemSetnmn2BLAST.OUT10书的复制源程序名BOOK.(PAS,C,CPP)可执行文件名BOOK.E某E输入文件名BOOK.IN 输出文件名 BOOK.OUT现在要把M本有顺序的书分给K个人复制(抄写)，每一个人的抄写 速度都一样，一本书不允许给两个(或以

8、上)的人抄写，分给每一个人的 书，必须是连续的，比如不能把第一、第三、第四本数给同一个人抄写。 现在请你设计一种方案，使得复制时间最短。复制时间为抄写页数最多的 人用去的时间。输入第一行两个整数 M、K；(K=M=100)第二行M个整数，第i个整数表示第i本书的页数。输出123456789BOOK.OUT156789最小乘车费用源程序名BUSSES.(PAS,C,CPP)可执行文件名BUSSES.E某E输入文件名 BUSSES.IN 输出文件名 BUSSES.OUT-4-DPProblemSet某条街上每一公里就有一汽车站，乘车费用如下表：公里数费用 112221331440549658769

9、87999010101而一辆汽车从不行驶超过10 公里。 某人想行驶 n 公里，假设他可以任意次换车，请你帮他找到一种乘车方案 使费用最小（10 公里的费用比 1 公里小的情况是允许的）。编一程序：从文件BUSSES.IN中读入对乘车费用的描述；算出最小的价格；把结果写入文件 BUSSES.OUT 中。输入输入文件共两行，第一行为10 个不超过100 的整数，依次表示行驶110公里的费用，相邻两数间用空格隔开；第二行为某人想要行驶的公 里数。输出输出文件仅一行包含一个整数，表示该测试点的最小费用。样例BUSSES.IN12213140495869799010115BUSSES.OUT147筷子

10、源程序名CHOP.(PAS,C,CPP)可执行文件名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,

11、0-5-DPProblemSet输出输出文件仅一行。如果凑不齐K+3双，输出-1,否则输出长度差平方和的 最小值。样例CH0P.IN101112333461020CHOP.OUT5 说明第一双11 第二双23第三双33第四双46(1-1厂2+(2-3厂2+(3-3厂2+(4-6厂2=5护卫队源程序名CONVOY.（PAS,C,CPP）可执行文件名CONVOY.E某E输入文件 名 CONVOY.IN 输出文件名 CONVOY.OUT输入文件第一行包含三个正整数（用空格隔开），第一个整数表示该桥 所能承受的最大载重量（用吨表示）；第二个整数表示该桥的长度（用千米 表示）；第三个整数表示该护卫队中车

12、辆的总数（n1000）。接下来的几行 中，每行包含两个正整数W和S （用空格隔开），W表示该车的重量（用吨表 示），S表示该车过桥能达到的最快速度（用千米/小时表示）。车子的重量 和速度是按车子排队等候时的顺序给出的。输出输出文件应该是一个实数，四舍五入精确到小数点后 1 位，表示整个 护卫车队通过该-6-DPProblemSet桥所需的最短时间（用分钟表示）。样例CONVOY.IN100510402550205020701012509704930382527501970CONVOY.OUT75.0DOLLARS源程序名DOLLARS.(PAS,C,CPP)可执行文件名DOLLARS.E某E输

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

14、差,结果在正确 结果 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 美元动态规划部分（初中组不作要求）潜水员（ga.e 某 e）潜水员为

15、了潜水要使用特殊的装备。他有一个带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 个气缸里的氧和氮的容量及汽缸 重量。输出格式仅一行包含一个整数,为潜水员完成工作所需的气