动态规划：NOIP的题目

DP Problem Set

顺序对齐

源程序名 ALIGN.??? (PAS,C,CPP) 可执行文件名 ALIGN.EXE 输入文件名 ALIGN.IN 输出文件名 ALIGN.OUT

考虑两个字符串右对齐的最佳解法。例如，有一个右对齐方案中字符串是AADDEFGGHC和ADCDEGH。

AAD_DEFGGHC ADCDE__GH_

每一个数值匹配的位置值2分，一段连续的空格值-1分。所以总分是匹配点的2倍减去连续空格的段数，在上述给定的例子中，6个位置(A,D,D,E,G,H)匹配，三段空格，所以得分2*6+(-1)*3=9，注意，我们并不处罚左边的不匹配位置。若匹配的位置是两个不同的字符，则既不得分也不失分。

请你写个程序找出最佳右对齐方案。 输入

输入文件包含两行，每行一个字符串，最长50个字符。字符全部是大字字母。 输出

一行，为最佳对齐的得分。 样例 ALIGN.IN

AADDEFGGHC ADCDEGH

ALIGN.OUT 9

_______________________________________________________________________________

任务安排

源程序名 BATCH.??? (PAS,C,CPP) 可执行文件名 BATCH.EXE 输入文件名 BATCH.IN 输出文件名 BATCH.OUT

N个任务排成一个序列在一台机器上等待完成（顺序不得改变），这N个任务被分成若干批，每批包含相邻的若干任务。从时刻0开始，这些任务被分批加工，第i个任务单独完成所需的时间是Ti。在每批任务开始前，机器需要启动时间S，而完成这批任务所需的时间是各个任务需要时间的总和（同一批任务将在同一时刻完成）。每个任务的费用是它的完成时刻乘以一个费用系数Fi。请确定一个分组方案，使得总费用最小。

- 1 -

DP Problem Set

例如：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及其费用系数Fi。 输出

一个数，最小的总费用。 样例 BATCH.IN 5 1 1 3 3 2 4 3 2 3 1 4

BATCH.OUT 153

_______________________________________________________________________________

最大的算式

源程序名 BIGEXP.??? (PAS,C,CPP) 可执行文件名 BIGEXP.EXE 输入文件名 BIGEXP.IN 输出文件名 BIGEXP.OUT

题目很简单，给出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之间）。

- 2 -

DP Problem Set

输出

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

BIGEXP.IN 5 2

1 2 3 4 5

BIGEXP.OUT 120 说明

(1+2+3)*4*5=120

_______________________________________________________________________________

BLAST

源程序名 BLAST.??? (PAS,C,CPP) 可执行文件名 BLAST.EXE 输入文件名 BLAST.IN 输出文件名 BLAST.OUT

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

如果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 -

DP Problem Set

snmn 2

BLAST.OUT 10

_______________________________________________________________________________

书的复制

源程序名 BOOK.??? (PAS,C,CPP) 可执行文件名 BOOK.EXE 输入文件名 BOOK.IN 输出文件名 BOOK.OUT

现在要把M本有顺序的书分给K个人复制（抄写），每一个人的抄写速度都一样，一本书不允许给两个（或以上）的人抄写，分给每一个人的书，必须是连续的，比如不能把第一、第三、第四本数给同一个人抄写。现在请你设计一种方案，使得复制时间最短。复制时间为抄写页数最多的人用去的时间。 输入

第一行两个整数M、K；（K<=M<=100）

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

共K行，每行两个正整数，第i行表示第i个人抄写的书的起始编号和终止编号。K行的起始编号应该从小到大排列，如果有多解，则尽可能让前面的人少抄写。 样例 BOOK.IN 9 3

1 2 3 4 5 6 7 8 9

BOOK.OUT 1 5 6 7 8 9

_______________________________________________________________________________

最小乘车费用

源程序名 BUSSES.??? (PAS,C,CPP) 可执行文件名 BUSSES.EXE 输入文件名 BUSSES.IN 输出文件名 BUSSES.OUT

- 4 -

DP Problem Set

某条街上每一公里就有一汽车站，乘车费用如下表： 公里数 费用 1 12 2 21 3 31 4 40 5 49 6 58 7 69 8 79 9 90 10 101 而一辆汽车从不行驶超过10公里。某人想行驶n公里，假设他可以任意次换车，请你帮他找到一种乘车方案使费用最小（10公里的费用比1公里小的情况是允许的）。

编一程序：

从文件BUSSES.IN中读入对乘车费用的描述； 算出最小的价格；

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

输入

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

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

BUSSES.IN

12 21 31 40 49 58 69 79 90 101 15

BUSSES.OUT 147

_______________________________________________________________________________

筷子

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

DP Problem Set

输出

输出文件仅一行。如果凑不齐K+3双，输出-1，否则输出长度差平方和的最小值。 样例 CHOP.IN 10 1

1 1 2 3 3 3 4 6 10 20

CHOP.OUT 5 说明

第一双 1 1 第二双 2 3 第三双 3 3 第四双 4 6

(1-1)^2+(2-3)^2+(3-3)^2+(4-6)^2=5

_______________________________________________________________________________

护卫队

源程序名 CONVOY.??? (PAS,C,CPP) 可执行文件名 CONVOY.EXE 输入文件名 CONVOY.IN 输出文件名 CONVOY.OUT

护卫车队在一条单行的街道前排成一队，前面河上是一座单行的桥。因为街道是一条单行道，所以任何车辆都不能超车。桥能承受一个给定的最大承载量。为了控制桥上的交通，桥两边各站一个指挥员。护卫车队被分成几个组，每组中的车辆都能同时通过该桥。当一组车队到达了桥的另一端，该端的指挥员就用电话通知另一端的指挥员，这样下一组车队才能开始通过该桥。每辆车的重量是已知的。任何一组车队的重量之和不能超过桥的最大承重量。被分在同一组的每一辆车都以其最快的速度通过该桥。一组车队通过该桥的时间是用该车队中速度最慢的车通过该桥所需的时间来表示的。问题要求计算出全部护卫车队通过该桥所需的最短时间值。 输入

输入文件第一行包含三个正整数(用空格隔开)，第一个整数表示该桥所能承受的最大载重量(用吨表示)；第二个整数表示该桥的长度(用千米表示)；第三个整数表示该护卫队中车辆的总数(n<1000)。接下来的几行中，每行包含两个正整数W和S(用空格隔开)，W表示该车的重量(用吨表示)，S表示该车过桥能达到的最快速度(用千米/小时表示)。车子的重量和速度是按车子排队等候时的顺序给出的。 输出

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

- 6 -

DP Problem Set

桥所需的最短时间(用分钟表示)。 样例

CONVOY.IN 100 5 10 40 25 50 20 50 20 70 10 12 50 9 70 49 30 38 25 27 50 19 70

CONVOY.OUT 75.0

_______________________________________________________________________________

DOLLARS

源程序名 DOLLARS.??? (PAS,C,CPP) 可执行文件名 DOLLARS.EXE 输入文件名 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.IN 5 400

- 7 -

DP Problem Set

300 500 300 250

DOLLARS.OUT 266.66

样例解释 (无需输出)

Day 1 ... changing 100.0000 美元= 400.0000 马克 Day 2 ... changing 400.0000 马克= 133.3333 美元 Day 3 ... changing 133.3333 美元= 666.6666 马克 Day 5 ... changing 666.6666 马克= 266.6666 美元

_______________________________________________________________________________

动态规划部分

（初中组不作要求）

潜水员

（gas.exe）

潜水员为了潜水要使用特殊的装备。他有一个带2种气体的气缸：一个为氧气，一个为氮气。让潜水员下潜的深度需要各种的数量的氧和氮。潜水员有一定数量的气缸。每个气缸都有重量和气体容量。潜水员为了完成他的工作需要特定数量的氧和氮。他完成工作所需气缸的总重的最低限度的是多少？

例如：潜水员有5个气缸。每行三个数字为：氧，氮的（升）量和气缸的重量：

3 36 120 10 25 129 5 50 250 1 45 130 4 20 119

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

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

输入格式

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

第一行有2整数t，a（1<=t<=21，1<=a<=79）。它们表示氧，氮各自需要的量。

- 8 -

DP Problem Set

第二行为整数n （1<=n<=1000）表示气缸的个数。

此后的n行，每行包括ti，ai，wi（1<=ti<=21，1<=ai<=79，1<=wi<=800）3整数。这些各自是：第i个气缸里的氧和氮的容量及汽缸重量。

输出格式

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

样例输入 5 60 5

3 36 120 10 25 129 5 50 250 1 45 130 4 20 119

样例输出 249

饥饿的奶牛

（hunger.exe）

John养了若干奶牛，每天晚上奶牛都要进食。由于条件比较简陋，并不一定所有奶牛都能吃到食物。奶牛的进食方式是这样的：John有n个食桶（1<=n<=2000），分别编号为1..n。这些食桶被按照编号排成一行。John将奶牛们分成若干组，每组奶牛总是呆在一起进食的，每组奶牛会提出要求——他们需要吃第start到第end桶中的食物。可能存在若干组奶牛都要吃同一个桶中的食物，从而就产生了冲突，这时John只能满足其中一组的要求，另一些组就只能饿肚子了。

John当然不想让奶牛都饿肚子，所以他希望根据奶牛们提出的请求，满足其中一些组的要求，使得最多的食桶被奶牛食用。这个难题困扰着John，他希望得到你的帮助。

输入格式

从文本文件hunger.in中读入数据。 第一行一个整数n，表示奶牛的组数。（1<=n<=1000）

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

输出格式

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

样例输入

- 9 -

DP Problem Set

3 1 3 7 8 3 4

样例输出 5

（满足第1组和第2组奶牛的要求，这样1~3号和7~8号这5个食桶可以被食用）

单词的划分

（word.exe）

有一个很长的由小写字母组成字符串。为了便于对这个字符串进行分析，需要将它划分成若干个部分，每个部分称为一个单词。出于减少分析量的目的，我们希望划分出的单词数越少越好。你就是来完成这一划分工作的。

输入格式

从文本文件word.in中读入数据。 第一行，一个字符串。（字符串的长度不超过100） 第二行一个整数n，表示单词的个数。（n<=100） 第3~n+2行，每行列出一个单词。

输出格式

一个整数，表示字符串可以被划分成的最少的单词数。

样例输入 realityour 5 real reality it your our

样例输出 2

（原字符串可拆成real+it+your或reality+our，由于reality+our仅为两个部分，因此最优解为2，另外注意，单词列表中的每个单词都可以重复使用多次，也可以不用）

火车票

- 10 -

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

_______________________________________________________________________________

胖男孩

源程序名 FATBOY.??? (PAS,C,CPP) 可执行文件名 FATBOY.EXE 输入文件名 FATBOY.IN 输出文件名 FATBOY.OUT

麦克正如我们所知的已快乐地结婚，在上个月他胖了70磅。因为手指上的脂肪过多，使他连给他最亲密的朋友斯拉夫克写一个电子邮件都很困难。 每晚麦克都详细地描述那一天他所吃的所有东西，但有时当他只想按一次某键时往往会

- 15 -

本文来源：https://www.bwwdw.com/article/vr2r.html