动态规划：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先生有很多双筷子。确切的说应该是很多根，因为筷子的长度不一，很难判断出哪 …… 此处隐藏：2132字，全部文档内容请下载后查看。喜欢就下载吧 ……