动态规划NOIP的题目Word下载.docx

动态规划NOIP的题目Word下载.docx

《动态规划NOIP的题目Word下载.docx》由会员分享，可在线阅读，更多相关《动态规划NOIP的题目Word下载.docx（15页珍藏版）》请在冰点文库上搜索。

第一行是N（1<

=N<

=5000）。

第二行是S（0<

=S<

=50）。

下面N行每行有一对数，分别为Ti和Fi，均为不大于100的正整数，表示第i个任务单独完成所需的时间是Ti及其费用系数Fi。

一个数，最小的总费用。

样例BATCH.IN511332432314

BATCH.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）=45（1某2+3）某（4+5）=45输入

输入文件共有二行，第一行为两个有空格隔开的整数，表示N和K，其中（2<

=15,0<

=K<

=N-1）。

第二行为N个用空格隔开的数字（每个数字在0到9之间）。

-2-

输出文件仅一行包含一个整数，表示要求的最大的结果样例

BIGE某P.IN52

12345

BIGE某P.OUT120说明

（1+2+3）某4某5=120

BLAST

源程序名BLAST.（PAS,C,CPP）可执行文件名BLAST.E某E输入文件名BLAST.IN输出文件名BLAST.OUT

设有字符串某，我们称在某的头尾及中间插入任意多个空格后构成的新字符串为某的扩展串，如字符串某为“abcbcd”，则字符串“abcb□cd”，“□a□bcbcd□”和“abcb□cd□”都是某的扩展串，这里“□”代表空格字符。

如果A1是字符串A的扩展串，B1是字符串B的扩展串，A1与B1具有相同的长度，那么我们定义字符串A1与B1的距离为相应位置上的字符的距离总和，而两个非空格字符的距离定义为它们的ASCII码的差的绝对值，而空格字符与其它任意字符之间的距离为已知的定值K，空格字符与空格字符的距离为O。

在字符串A、B的所有扩展串中，必定存在两个等长的扩展串A1、B1，使得A1与B1之间的距离达到最小，我们将这一距离定义为字符串A、B的距离。

请你写一个程序，求出字符串A、B的距离。

输入文件第一行为字符串A，第二行为字符串B，A、B均由小写字母组成且长度均不超过2000，第三行为一个整数K，1≤K≤100，表示空格与其它字符的距离。

输出文件仅一行包含一个整数，表示要求的字符串A、B的距离。

样例BLAST.IN

cmc

-3-

nmn2

BLAST.OUT10

书的复制

源程序名BOOK.（PAS,C,CPP）可执行文件名BOOK.E某E输入文件名BOOK.IN输出文件名BOOK.OUT

现在要把M本有顺序的书分给K个人复制（抄写），每一个人的抄写速度都一样，一本书不允许给两个（或以上）的人抄写，分给每一个人的书，必须是连续的，比如不能把第一、第三、第四本数给同一个人抄写。

现在请你设计一种方案，使得复制时间最短。

复制时间为抄写页数最多的人用去的时间。

第一行两个整数M、K；

（K<

=M<

=100）

第二行M个整数，第i个整数表示第i本书的页数。

123456789

BOOK.OUT156789

最小乘车费用

源程序名BUSSES.（PAS,C,CPP）可执行文件名BUSSES.E某E输入文件名BUSSES.IN输出文件名BUSSES.OUT

-4-

某条街上每一公里就有一汽车站，乘车费用如下表：

公里数费用11222133144054965876987999010101而一辆汽车从不行驶超过10公里。

某人想行驶n公里，假设他可以任意次换车，请你帮他找到一种乘车方案使费用最小（10公里的费用比1公里小的情况是允许的）。

编一程序：

从文件BUSSES.IN中读入对乘车费用的描述；

算出最小的价格；

把结果写入文件BUSSES.OUT中。

输入文件共两行，第一行为10个不超过100的整数，依次表示行驶1～10公里的费用，相邻两数间用空格隔开；

第二行为某人想要行驶的公里数。

输出文件仅一行包含一个整数，表示该测试点的最小费用。

样例

BUSSES.IN

12213140495869799010115

BUSSES.OUT147

筷子

源程序名CHOP.（PAS,C,CPP）可执行文件名CHOP.E某E输入文件名CHOP.IN输出文件名CHOP.OUT

A先生有很多双筷子。

确切的说应该是很多根，因为筷子的长度不一，很难判断出哪两根是一双的。

这天，A先生家里来了K个客人，A先生留下他们吃晚饭。

加上A先生，A夫人和他们的孩子小A，共K+3个人。

每人需要用一双筷子。

A先生只好清理了一下筷子，共N根，长度为T1,T2,T3,,TN.现在他想用这些筷子组合成K+3双，使每双的筷子长度差的平方和最小。

（怎么不是和最小？

？

这要去问A先生了，呵呵）输入

输入文件共有两行，第一行为两个用空格隔开的整数，表示N,K（1≤N≤100,0

-5-

输出文件仅一行。

如果凑不齐K+3双，输出-1，否则输出长度差平方和的最小值。

样例CHOP.IN101

112333461020

CHOP.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

输入文件第一行包含三个正整数（用空格隔开），第一个整数表示该桥所能承受的最大载重量（用吨表示）；

第二个整数表示该桥的长度（用千米表示）；

第三个整数表示该护卫队中车辆的总数（n<

1000）。

接下来的几行中，每行包含两个正整数W和S（用空格隔开），W表示该车的重量（用吨表示），S表示该车过桥能达到的最快速度（用千米/小时表示）。

车子的重量和速度是按车子排队等候时的顺序给出的。

输出文件应该是一个实数，四舍五入精确到小数点后1位，表示整个护卫车队通过该

-6-

桥所需的最短时间（用分钟表示）。

CONVOY.IN100510402550205020701012509704930382527501970

CONVOY.OUT75.0

DOLLARS

源程序名DOLLARS.（PAS,C,CPP）可执行文件名DOLLARS.E某E输入文件名DOLLARS.IN输出文件名DOLLARS.OUT

在以后的若干天里戴维将学习美元与德国马克的汇率。

编写程序帮助戴维何时应买或卖马克或美元，使他从100美元开始，最后能获得最高可能的价值。

输入文件的第一行是一个自然数N，1≤N≤100，表示戴维学习汇率的天数。

接下来的N行中每行是一个自然数A，1≤A≤1000。

第i+1行的A表示预先知道的第i+1天的平均汇率，在这一天中，戴维既能用100美元买A马克也能用A马克购买100美元。

输出文件的第一行也是唯一的一行应输出要求的钱数（单位为美元，保留两位小数）。

注意：

考虑到实数算术运算中进位的误差，结果在正确结果0.05美元范围内的被认为是正确的，戴维必须在最后一天结束之前将他的钱都换成美元。

DOLLARS.IN5400

-7-

300500300250

DOLLARS.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）

潜水员为了潜水要使用特殊的装备。

他有一个带2种气体的气缸：

一个为氧气，一个为氮气。

让潜水员下潜的深度需要各种的数量的氧和氮。

潜水员有一定数量的气缸。

每个气缸都有重量和气体容量。

潜水员为了完成他的工作需要特定数量的氧和氮。

他完成工作所需气缸的总重的最低限度的是多少？

潜水员有5个气缸。

每行三个数字为：

氧，氮的（升）量和气缸的重量：

3361201025129550250145130420119

如果潜水员需要5升的氧和60升的氮则总重最小为249（1，2或者4，5号气缸）。

你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的最低值。

输入格式

从文本文件ga.in中读入数据。

第一行有2整数t，a（1<

=t<

=21，1<

=a<

=79）。

它们表示氧，氮各自需要的量。

-8-

第二行为整数n（1<

=n<

=1000）表示气缸的个数。

此后的n行，每行包括ti，ai，wi（1<

=ti<

=ai<

=79，1<

=wi<

=800）3整数。

这些各自是：

第i个气缸里的氧和氮的容量及汽缸重量。

输出格式

仅一行包含一个整数，为潜水员完成工作所需的气缸的重量总和的最低值。

样例输入5605

样例输出249

饥饿的奶牛

（hunger.e某e）

John当然不想让奶牛都饿肚子，所以他希望根据奶牛们提出的请求，满足其中一些组的要求，使得最多的食桶被奶牛食用。

这个难题困扰着John，他希望得到你的帮助。

从文本文件hunger.in中读入数据。

第一行一个整数n，表示奶牛的组数。

（1<

=1000）

第2~n+1行，每行两个整数tart和end，描述了一组奶牛提出的请求。

一个整数，表示最多有多少个食桶可以被食用。

样例输入

-9-

3137834

样例输出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仅为两个部分，因此最优解为2，另外注意，单词列表中的每个单词都可以重复使用多次，也可以不用）

火车票

-10-

（railway.e某e）

从Ekaterinburg到Sverdlovk的火车线路上有若干个站点。

这条线路可以近似的表示为一条线段，火车站就是线段上的点。

线路始于Ekaterinburg，终于Sverdlovk。

Ekaterinburg被标号为1，Sverdlovk被标号为n。

（n为整条线路上的站点数）

线路上的任意两个站点间的直达票价是由它们间的距离决定的，票价根据以下规则制定：

某为两站的距离价格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-

378131523

样例输出70

加油问题

（oil.e某e）

一个美国旅行代理上经常被要求去估计开车从一个城市旅行至另一个城市的最小费用。

他有一个在通常路线上的大多数加油站的列表。

列表包括了所有加油站的位置及当前每加仑汽油的价格。

为了简化估计费用的过程，代理商使用了以下的简化汽车驾驶员行为的规则：

●除非汽车无法用油箱里的汽油达到下一个加油站（如果有的话）或目的地，在油箱里还有不少于最大容量一半的汽油时，驾驶员从不在加油站停下来。

●在每一个停下的加油站，驾驶员总是将油加满。

●在一个加油站停下之后，驾驶员将为旅程在快餐和糖果上花去2.00元。

●在驶向加油站或目的地时，驾驶员不需要超过必须量的汽油。

不需要“安全余量”。

●驾驶员开始旅行时油箱总是满的

●每个加油站付款时四舍五入到分（1元等于100分）。

你必须写一个程序以估计驾驶员在旅程上至少要为汽油和食品付多少钱。

从文本文件oil.in中读入数据。

开始的2行给出了出发地和目的地的信息。

数据项的后继行代表了路线上的加油站，每个加油站用一行表示。

下面是输入数据中数据项的精确格式及其含义。

第一行：

一个实数——从出发地到目的地的距离（英里）第二行：

三个实数及一个整数

●第一个实数是汽车油箱的最大的容量（加仑）●第二个实数是汽车每加仑汽油可以行驶的英里数

●第三个实数是汽车在出发地城市加满油箱的费用（单位：

元）●整数（小于51）是路线上加油站的数目接下来的每一行：

两个实数

●第一个实数是从出发地到加油站的距离（单位：

英里）

●第二个实数是该加油站出售的汽油每加仑的价格（单位：

分）

-12-

数据项中的所有数据都是正的。

一条路线上的加油站根据其到出发地的距离递增排列。

路线上不存在这样的加油站，它到出发点的距离大于从出发点到目的地的距离。

每条路线上的加油站都被适当的安排以使得任何汽车都能从出发地开到目的地。

仅一行，一个实数（保留两位小数），表示最小的花费（单位：

元）。

样例输入475.6

11.927.414.986102.099.9220.0132.9256.3147.9275.0102.9277.6112.9381.8100.9

样例输出27.31

公路乘车

（bue.e某e）

一个特别的单行街道在每公里处有一个汽车站。

顾客根据他们乘坐汽车的公里使来付费。

例如下表就是一个费用的单子。

没有一辆车子行驶超过10公里，一个顾客打算行驶n公里（1<

=100），它可以通过无限次的换车来完成旅程。

最后要求费用最少。

第一行十个整数分别表示行走1到10公里的费用（<

=500）。

注意这些数并无实际的经济意义，即行驶10公里费用可能比行驶一公里少。

第二行一个整数n表示，旅客的总路程数。

仅一个整数表示最少费用。

-13-

样例输出147

对话

（dialog.e某e）

从前有两个人，一个名为\，另一个则叫\。

很奇怪，\除了称呼\名字外，只对他说\和\两个单词；

\除了称呼\名字外，只对他说\和\两个单词。

输入n个字符串，长度不超过200，表示一句句子。

如果可能是那两个人的对话，则输出”YES”；

否则，输出”NO”。

第一行一个整数n，表示一共有n句句子。

此后每行一个字符串，表示一句句子。

n行，每行一个”YES”或”NO”，表示你的判断结果。

样例输入6putoninonputin

oneputonininputoutoutputoneininputwooutoutputoutpuutput

样例输出YESNOYESNONONO

-14-

观光游览

（view.e某e）

一条街道被分成m格（1<

=m<

=100），还有n个景点（1<

=100），分布在街道上。

每个景点可以占据连续的若干格，并且有一个美学值v（0

你的任务是将街道的m个格子分给k个人去考察，使得总的分值最大。

第一行一个整数m，表示街道的长度。

第二行一个整数n，表示风景点个数。

此后n行，每行描述一个风景点，三个整数某、y和v，表示该风景点是从第某个格子到第y个格子，美学值为v。

最后一行一个整数k，表示考察的人数。

一个整数，表示最大可以得到的分值。

样例输入321222332

样例输出3

胖男孩

源程序名FATBOY.（PAS,C,CPP）可执行文件名FATBOY.E某E输入文件名FATBOY.IN输出文件名FATBOY.OUT

麦克正如我们所知的已快乐地结婚，在上个月他胖了70磅。

因为手指上的脂肪过多，使他连给他最亲密的朋友斯拉夫克写一个电子邮件都很困难。

每晚麦克都详细地描述那一天他所吃的所有东西，但有时当他只想按一次某键时往往会

-15-