动态规划：NOIP的题目(4)

DP Problem Set

（railway.exe）

从Ekaterinburg到Sverdlovsk的火车线路上有若干个站点。这条线路可以近似的表示为一条线段，火车站就是线段上的点。线路始于Ekaterinburg，终于Sverdlovsk。Ekaterinburg被标号为1，Sverdlovsk被标号为n。（n为整条线路上的站点数）

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

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

第三行两个整数s和t，分别是起点和终点的编号。注意：s不一定小于t。 以下的n-1行，按据Ekaterinburg远近，每行描述了一个车站的位置。它包含一个整数，表示该车站据Ekaterinburg的距离。

任意两个车站的距离不超过10^9，任意两个相邻的车站的距离不超过L3。

输出格式

一个整数，表示从给定的一个站到给定的另一个站的最小花费。

样例输入 3 6 8 20 30 40 7 2 6

- 11 -

DP Problem Set

3 7 8 13 15 23

样例输出 70

加油问题

（oil.exe）

一个美国旅行代理上经常被要求去估计开车从一个城市旅行至另一个城市的最小费用。他有一个在通常路线上的大多数加油站的列表。列表包括了所有加油站的位置及当前每加仑汽油的价格。

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

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

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

●在一个加油站停下之后，驾驶员将为旅程在快餐和糖果上花去2.00元。 ●在驶向加油站或目的地时，驾驶员不需要超过必须量的汽油。不需要“安全余量”。

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

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

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

输入格式

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

开始的2行给出了出发地和目的地的信息。数据项的后继行代表了路线上的加油站，每个加油站用一行表示。下面是输入数据中数据项的精确格式及其含义。 第一行：一个实数——从出发地到目的地的距离（英里） 第二行：三个实数及一个整数

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

●第三个实数是汽车在出发地城市加满油箱的费用（单位：元） ●整数（小于51）是路线上加油站的数目 接下来的每一行：两个实数

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

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

- 12 -

DP Problem Set

数据项中的所有数据都是正的。一条路线上的加油站根据其到出发地的距离递增排列。路线上不存在这样的加油站，它到出发点的距离大于从出发点到目的地的距离。每条路线上的加油站都被适当的安排以使得任何汽车都能从出发地开到目的地。

输出格式

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

样例输入 475.6

11.9 27.4 14.98 6 102.0 99.9 220.0 132.9 256.3 147.9 275.0 102.9 277.6 112.9 381.8 100.9

样例输出 27.31

公路乘车

（buses.exe）

一个特别的单行街道在每公里处有一个汽车站。顾客根据他们乘坐汽车的公里使来付费。例如下表就是一个费用的单子。

没有一辆车子行驶超过10公里，一个顾客打算行驶n公里（1<=n<=100），它可以通过无限次的换车来完成旅程。最后要求费用最少。

输入格式

第一行十个整数分别表示行走1到10公里的费用（<=500）。注意这些数并无实际的经济意义，即行驶10公里费用可能比行驶一公里少。 第二行一个整数n表示，旅客的总路程数。

输出格式

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

样例输入

12 21 31 40 49 58 69 79 90 101 15

- 13 -

DP Problem Set

样例输出 147

对话

（dialog.exe）

从前有两个人，一个名为\，另一个则叫\。很奇怪，\除了称呼\名字外，只对他说\和\两个单词；\除了称呼\名字外，只对他说\和\两个单词。

最近人们在研究他们对话，但是，由于资料的混乱，其中可能有一些不是他们的对话。你的任务是鉴别一些句子，判断这些句子是否可能是他们的对话。（即，判断句子是否可以被划分成若干单词，这些单词只可以是\、\、\、\、\和\）。

输入n个字符串，长度不超过200，表示一句句子。如果可能是那两个人的对话，则输出”YES”；否则，输出”NO”。

输入格式

第一行一个整数n，表示一共有n句句子。 此后每行一个字符串，表示一句句子。

输出格式

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

样例输入 6 puton inonputin

oneputonininputoutoutput oneininputwooutoutput outpu utput

样例输出 YES NO YES NO NO NO

- 14 -

DP Problem Set

观光游览

（view.exe）

一条街道被分成m格（1<=m<=100），还有n个景点（1<=n<=100），分布在街道上。每个景点可以占据连续的若干格，并且有一个美学值v（0

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

输入格式

第一行一个整数m，表示街道的长度。 第二行一个整数n，表示风景点个数。

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

输出格式

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

样例输入 3 2 1 2 2 2 3 3 2

样例输出 3

_______________________________________________________________________________

胖男孩

源程序 …… 此处隐藏：1226字，全部文档内容请下载后查看。喜欢就下载吧 ……