顺序对齐
源程序名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个任务单独完成所需的时间是T i。在每批任务开始前，机器需要启动时间S，而完成这批任务所需的时间是各个任务需要时间的总和（同一批任务将在同一时刻完成）。每个任务的费用是它的完成时刻乘以一个费用系数F i。请确定一个分组方案，使得总费用最小。
例如：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行每行有一对数，分别为T i和F i，均为不大于100的正整数，表示第i个任务单独完成所需的时间是T i及其费用系数F i。
输出
一个数，最小的总费用。
样例
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之间）。
输出
输出文件仅一行包含一个整数，表示要求的最大的结果
样例
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
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
帮他找到一种乘车方案使费用最小（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 输出 输出文件仅一行。如果凑不齐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位，表示整个护卫车队通过该 桥所需的最短时间(用分钟表示)。 样例 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 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）。它们表示氧，氮各自需要的量。 第二行为整数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，描述了一组奶牛提出的请求。 输出格式 一个整数，表示最多有多少个食桶可以被食用。 样例输入 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，另外注意，单词列表中的每个单词都可以重复使用多次，也可以不用） 火车票 （railway.exe） 从Ekaterinburg到Sverdlovsk的火车线路上有若干个站点。这条线路可以近似的表示为一条线段，火车站就是线段上的点。线路始于Ekaterinburg，终于Sverdlovsk。Ekaterinburg被标号为1，Sverdlovsk被标号为n。（n为整条线路上的站点数） 线路上的任意两个站点间的直达票价是由它们间的距离决定的，票价根据以下规则制定： 如果两站的间距超过L3，则无直达车票。所以有时可能有必要买多张票，通过转车的方式，从一个站到达另一个站。 例如，在上面的图中，有7个站点。2号站点到6号站点的距离超过L3，不能买直达票。存在若干种中转的方法，其中的一种是买两张票：先花费C2从2号站到达3号站，然后花费C3从3号站到6号站，一种花费C2+C3。 你的任务是，找出一种最经济的中转方案。 输入格式 从文本文件railway.in中读入数据。 第一行6个整数L1, L2, L3, C1, C2, C3（1<=L1 第二行一个整数n（2<=n<=100），表示线路上的车站数。 第三行两个整数s和t，分别是起点和终点的编号。注意：s不一定小于t。 以下的n-1行，按据Ekaterinburg远近，每行描述了一个车站的位置。它包含一个整数，表示该车站据Ekaterinburg的距离。 任意两个车站的距离不超过10^9，任意两个相邻的车站的距离不超过L3。 输出格式 一个整数，表示从给定的一个站到给定的另一个站的最小花费。 样例输入 3 6 8 20 30 40 7 2 6 3 7 8 13 15 23 样例输出 70 加油问题 （oil.exe） 一个美国旅行代理上经常被要求去估计开车从一个城市旅行至另一个城市的最小费用。他有一个在通常路线上的大多数加油站的列表。列表包括了所有加油站的位置及当前每加仑汽油的价格。 为了简化估计费用的过程，代理商使用了以下的简化汽车驾驶员行为的规则： ●除非汽车无法用油箱里的汽油达到下一个加油站（如果有的话）或目的地， 在油箱里还有不少于最大容量一半的汽油时，驾驶员从不在加油站停下来。 ●在每一个停下的加油站，驾驶员总是将油加满。 ●在一个加油站停下之后，驾驶员将为旅程在快餐和糖果上花去2.00元。 ●在驶向加油站或目的地时，驾驶员不需要超过必须量的汽油。不需要“安 全余量”。 ●驾驶员开始旅行时油箱总是满的 ●每个加油站付款时四舍五入到分（1元等于100分）。 你必须写一个程序以估计驾驶员在旅程上至少要为汽油和食品付多少钱。 输入格式 从文本文件oil.in中读入数据。 开始的2行给出了出发地和目的地的信息。数据项的后继行代表了路线上的加油站，每个加油站用一行表示。下面是输入数据中数据项的精确格式及其含义。 第一行：一个实数——从出发地到目的地的距离（英里） 第二行：三个实数及一个整数 ●第一个实数是汽车油箱的最大的容量（加仑） ●第二个实数是汽车每加仑汽油可以行驶的英里数 ●第三个实数是汽车在出发地城市加满油箱的费用（单位：元） ●整数（小于51）是路线上加油站的数目 接下来的每一行：两个实数 ●第一个实数是从出发地到加油站的距离（单位：英里） ●第二个实数是该加油站出售的汽油每加仑的价格（单位：分） 数据项中的所有数据都是正的。一条路线上的加油站根据其到出发地的距离递增排列。路线上不存在这样的加油站，它到出发点的距离大于从出发点到目的地的距离。每条路线上的加油站都被适当的安排以使得任何汽车都能从出发地开到目的地。 输出格式 仅一行，一个实数（保留两位小数），表示最小的花费（单位：元）。 样例输入 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 样例输出 147 对话 （dialog.exe） 从前有两个人，一个名为"one"，另一个则叫"puton"。很奇怪，"one"除了称呼"puton"名字外，只对他说"out"和"output"两个单词；"puton"除了称呼"one"名字外，只对他说"in"和"input"两个单词。 最近人们在研究他们对话，但是，由于资料的混乱，其中可能有一些不是他们的对话。你的任务是鉴别一些句子，判断这些句子是否可能是他们的对话。（即，判断句子是否可以被划分成若干单词，这些单词只可以是"one"、"puton"、"out"、"output"、"in"和"input"）。 输入n个字符串，长度不超过200，表示一句句子。如果可能是那两个人的对话，则输出”YES”；否则，输出”NO”。 输入格式 第一行一个整数n，表示一共有n句句子。 此后每行一个字符串，表示一句句子。 输出格式 n行，每行一个”YES”或”NO”，表示你的判断结果。 样例输入 6 puton inonputin oneputonininputoutoutput oneininputwooutoutput outpu utput 样例输出 YES NO YES NO NO NO 观光游览 （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磅。因为手指上的脂肪过多，使他连给他最亲密的朋友斯拉夫克写一个电子邮件都很困难。 每晚麦克都详细地描述那一天他所吃的所有东西，但有时当他只想按一次某键时往往会 按了不止一次，并且他的胖手指还会碰到他不想要按的键，麦克也知道自己的手指有问题，因此他在打字的时候很小心，以确保每打一个想要的字符时误打的字符不超过3个，误打的字符可能在正确字符之前也可能在其之后。 当斯拉夫克多次收到读不懂的电子邮件后，他总是要求麦克将电子邮件发3遍，使他容易读懂一点。 编写程序，帮助斯拉夫克根据他所收到的三封电子邮件求出麦克可能写出的最长的信。 输入 输入文件包含了三行文本。每一行文本包括麦克信件的一种版本。其中所有的字符都由英文字母表中的小写字母组成并且不超过100个。 输出 输出文件中第一行即唯一的一行数据应该包含斯拉夫克根据所收到的电子邮件推测出的最长信件。你可以相信问题一定有解，但解不一定是唯一的。 样例 FATBOY.IN cecqbhvaiaedpibaluk cabegviapcihlaaugck adceevfdadaepcialaukd FATBOY.OUT cevapiluk _______________________________________________________________________________ 文件排版 源程序名FORMAT.??? (PAS,C,CPP) 可执行文件名 FORMAT.EXE 输入文件名 FORMAT.IN 输出文件名 FORMAT.OUT 写电子邮件是有趣的，但不幸的是经常写不好看，主要是因为所有的行不一样长，你的上司想要发排版精美的电子邮件，你的任务是为他编写一个电子邮件排版程序。 完成这个任务最简单的办法是在太短的行中的单词之间插入空格，但这并不是最好的方法，考虑如下例子： **************************** This is the example you are actually considering. 假设我们想将第二行变得和第一行一样长，靠简单地插入空格则我们将得到如下结果：**************************** This is the example you are actually considering. 但这太难看了，因为在第二行中有一个非常大的空白，如果将第一行的单词“are”移到下一行我们将得到较好的结果： **************************** This is the example you are actually considering. 当然，这必须对难看程度进行量化。因此我们必须给出单词之间的空格的难看程度，一个包含N个空格符的空白段，其难看程度值为(n-1)2，程序的目的是使难看程度的总和最小化。例如，第一个例子的难看程度是1+7*7=50，而第二个例子的难看程度仅为1+1+1+4+1+4=12。 输出时，每一行的开头和结尾处都必须是一个单词，即每行开头和结尾处不能有空白。唯一例外的是该行仅有一个单词组成的情况，对于这种情况你可将单词放在该行开头处输出，此时如果该单词比该行应有的长度短则我们指定它的最坏程度为500，当然在这种情况下，该行的实际长度即为该单词的长度。 输入 输入文件第一行是一个整数N，表示该段要求达到的宽度，1<=N<=80。该段文章由一个或多个单词组成，单词由ASCII码值为33到126（包含33和126）的字符组成，单词与单词之间用空格隔开（可能超过一个）。单词长度不会超过段落要求达到的宽度。一段文字所有单词的总长度不会超过10000个字符，任何一行都不会超过100个字符，任何一个单词都在同一行内。 输出 对于每个段落，找出使其难看程度最小的排版形式并输出句子：“Minimal badness is B.”,B是指按可能的最好排版形式会发生的难看程度值。注意排版后文本行数任意，多余的空格也可删除。 样例 FORMAT.IN 28 This is the example you are actually considering. FORMAT.OUT Minimal badness is 12. _______________________________________________________________________________ 相似基因 源程序名GENE.??? (PAS,C,CPP) 可执行文件名GENE.EXE 输入文件名GENE.IN 输出文件名 GENE.OUT 大家都知道，基因可以看作一个碱基对序列。它包含了4种核苷酸，简记作A,C,G,T。生物学家正致力于寻找人类基因的功能，以利用于诊断疾病和发明药物。 在一个人类基因工作组的任务中，生物学家研究的是：两个基因的相似程度。因为这个研究对疾病的治疗有着非同寻常的作用。两个基因的相似度的计算方法如下：对于两个已知基因，例如AGTGATG和GTTAG，将它们的碱基互相对应。当然，中间可以加入一些空碱基-，例如： 这样,两个基因之间的相似度就可以用碱基之间相似度的总和来描述，碱基之间的相似度如下表所示： 那么相似度就是：(-3)+5+5+(-2)+(-3)+5+(-3)+5=9。因为两个基因的对应方法不唯一，例如又有： 相似度为：(-3)+5+5+(-2)+5+(-1)+5=14。规定两个基因的相似度为所有对应方法中，相似度最大的那个。 输入 共两行。每行首先是一个整数，表示基因的长度；隔一个空格后是一个基因序列，序列中只含A,C,G,T四个字母。1<=序列的长度<=100。 输出 仅一行，即输入基因的相似度。 样例 GENE.IN 7 AGTGATG 5 GTTAG GENE.OUT 14 饥饿的牛 源程序名HUNGER.??? (PAS,C,CPP) 可执行文件名HUNGER.EXE 输入文件名HUNGER.IN 输出文件名 HUNGER.OUT 牛在饲料槽前排好了队。饲料槽依次用1到N(1<=N<=2000)编号。每天晚上，一头幸运的牛根据约翰的规则，吃其中一些槽里的饲料。 约翰提供B个区间的清单。一个区间是一对整数start-end,1<=start<=end<=N，表示一些连续的饲料槽，比如1-3,7-8,3-4等等。牛可以任意选择区间，但是牛选择的区间不能有重叠。 当然，牛希望自己能够吃得越多越好。给出一些区间，帮助这只牛找一些区间，使它能吃到最多的东西。 在上面的例子中，1-3和3-4是重叠的；聪明的牛选择{1-3，7-8}，这样可以吃到5个槽里的东西。 输入 第一行，整数B(1<=B<=1000) 第2到B+1行，每行两个整数，表示一个区间，较小的端点在前面。 输出 仅一个整数，表示最多能吃到多少个槽里的食物。 样例 HUNGER.IN 3 1 3 7 8 3 4 HUNGER.OUT 5 _______________________________________________________________________________ 递增序列(INCNEASING SEQUENCES) 源程序名INCSQ.??? (PAS,C,CPP) 可执行文件名INCSQ.EXE 输入文件名INCSQ.IN 输出文件名 INCSQ.OUT 给定一个数字串，请你插入若干个逗号，使得该数字串成为一个严格递增的数列且最后一个数要尽可能小，在这个问题中，前导的零是允许出现在数的前面的。 输入 输入数据仅含一行，为一个长度不超过80的数字串。 输出 输出一个严格递增且最后一数最小的数列，相邻两个数之间用一个逗号隔开，如果有多个数列满足要求，则输出第一个数最大的那个数列，若这样的解还不止一个，则输出第二个数最大的那个数列，以此类推。 样例 INCSQ.IN 100000101 INCSQ.OUT 100,000101 _______________________________________________________________________________ 奇怪的电梯 源程序名LIFT.??? (PAS,C,CPP) 可执行文件名 LIFT.EXE 输入文件名 LIFT.IN 输出文件名 LIFT.OUT 呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第i层楼(1<=i<=N)上有一个数字Ki(0<=Ki<=N)。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如：3 3 1 2 5代表了Ki(K1=3,K2=3,……)，从一楼开始。在一楼，按“上”可以到4楼，按“下”是不起作用的，因为没有-2楼。那么，从A楼到B楼至少要按几次按钮呢？ 输入 输入文件共有二行，第一行为三个用空格隔开的正整数，表示N,A,B(1≤N≤200, 1≤A,B≤N)，第二行为N个用空格隔开的正整数，表示Ki。 输出 输出文件仅一行，即最少按键次数,若无法到达，则输出-1。 样例 LIFT.IN 5 1 5 3 3 1 2 5 LIFT.OUT 3 例1：机器负荷分配问题 某公司新购进1000台机床，每台机床都可在高、低两种不同的负荷下进行生产，设在高负荷下生产的产量函数为g(x )=10x （单位：百件），其中x 为投入生产的机床数量，年完好率为a =0.7；在低负荷下生产的产量函数为h(y)=6y （单位：百件），其中y 为投人生产的机床数量，年完好率为b=0.9。计划连续使用5年，试问每年如何安排机床在高、低负荷下的生产计划，使在五年内生产的产品总产量达到最高。 例2：某企业通过市场调查，估计今后四个时期市场对某种产品的需要量如下表： 时期(k) 1 2 3 4 需要量(d k ) 2（单位） 3 2 4 假定不论在任何时期，生产每批产品的固定成本费为3(千元)，若不生产，则为零；生产单位产品成本费为1(千元)；每个时期生产能力所允许的最大生产批量为不超过6个单位，则任何时期生产x 个单位产品的成本费用为： 若 0＜x ≤6 ， 则生产总成本＝3十1·x 若 x ＝0 ， 则生产总成本＝0 又设每个时期末未销售出去的产品，在一个时期内单位产品的库存费用为0.5(千元)，同时还假定第1时期开始之初和在第4个时期之末，均无产品库存。现在我们的问题是；在满足上述给定的条件下，该厂如何安排各个时期的生产与库存，使所花的总成本费用最低？ 例3：设某企业在第一年初购买一台新设备，该设备在五年内的年运行收益、年运行费用及更换新设备的净费用如下表：（单位：万元） 年份(k) 役龄(t) 运行收益()k g t 运行费用()k r t 更新费用()k c t 第一年 0 22 6 18 第二年 0 1 23 21 6 8 19 22 动态规划： 【1】.矩阵乘法链，最小乘法次数。 一、问题描述 给定一个矩阵序列 动态规划讲解大全 动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作。 动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。 虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。 动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。 基本模型 多阶段决策过程的最优化问题。 在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。当然，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展，当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线，如图所示：（看词条图） 这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题就称为多阶段决策问题。 记忆化搜索 给你一个数字三角形, 形式如下: 1 2 3 4 5 6 7 8 9 10 找出从第一层到最后一层的一条路,使得所经过的权值之和最小或者最大. 无论对与新手还是老手，这都是再熟悉不过的题了，很容易地，我们写出状态转移方程：f(i, j)=a[i, j] + min{f(i+1, j)，f(i+1, j + 1)} 对于动态规划算法解决这个问题，我们根据状态转移方程和状态转移方向，比较容易地写出动态规划的循环表示方法。但是，当状态和转移非常复杂的时候，也许写出循环式的动态规划就不是那么 NOIP 2017全国青少年信息学奥林匹克联赛提高组初赛试题答案 ? 一、单项选择题（共 15 题，每题 1.5 分，共计 22.5 分；每题有且仅有一个正确选项）? 1. 从( )年开始，NOIP 竞赛将不再支持 Pascal 语言。 A. 2020 B. 2021 C. 2022 D. 2023 ? 2.在 8 位二进制补码中，10101011 表示的数是十进制下的( )。 A. 43 B. -85 C. -43 D.-84 ? 3.分辨率为 1600x900、16 位色的位图，存储图像信息所需的空间为( )。 A. 2812.5KB B. 4218.75KB C. 4320KB D. 2880KB ? 4. 2017年10月1日是星期日，1949年10月1日是( )。 A. 星期三 B. 星期日 C. 星期六 D. 星期二 ? 5. 设 G 是有 n 个结点、m 条边(n ≤m)的连通图，必须删去 G 的( )条边，才能使得 G 变成一棵树。 A.m–n+1 B. m-n C. m+n+1 D.n–m+1 ? 6. 若某算法的计算时间表示为递推关系式： T(N)=2T(N/2)+NlogN T(1)=1 则该算法的时间复杂度为( )。 A.O(N) B.O(NlogN) C.O(N log2N) D.O(N2) ? 7. 表达式a * (b + c) * d的后缀形式是()。 A. abcd*+* B. abc+*d* C. a*bc+*d D. b+c*a*d ? 8. 由四个不同的点构成的简单无向连通图的个数是( )。 A. 32 B. 35 C. 38 D. 41 ? 9. 将7个名额分给4个不同的班级，允许有的班级没有名额，有( )种不同的分配方案。 A. 60 B. 84 C. 96 D.120 ? 10. 若f[0]=0, f[1]=1, f[n+1]=(f[n]+f[n-1])/2，则随着i的增大，f[i]将接近与( )。 A. 1/2 B. 2/3 D. 1 ? 11. 设A和B是两个长为n的有序数组，现在需要将A和B合并成一个排好序的数组，请问任何以元素比较作为基本运算的归并算法最坏情况下至少要做( )次比较。 A. n2 B. nlogn C. 2n D.2n-1 ? 12. 在n(n>=3)枚硬币中有一枚质量不合格的硬币（质量过轻或质量过重），如果只有一架天平可以用来称重且称重的硬币数没有限制，下面是找出这枚不合格的硬币的算法。请把 a-c三行代码补全到算法中。 a. A XUY b. A Z c. n |A| 算法Coin(A,n) 1. k n/3 2. 将A中硬币分成X,Y,Z三个集合，使得|X|=|Y|=k, |Z|=n-2k 3. if W(X)≠W(Y) //W(X), W(Y)分别为X或Y的重量 4. then_______ 5. else_______ 6. __________ 7. if n>2 then goto 1 8. if n=2 then 任取A中1枚硬币与拿走硬币比较，若不等，则它不合格；若相等，则A 中剩下的硬币不合格 9. if n=1 then A中硬币不合格 正确的填空顺序是( )。 A. b,c,a B. c,b,a C. c,a,b D.a,b,c ? 算法总结 一、动态规划和递推 dp一般的解题步骤： 分析问题，弄清题意——从原问题中抽象出模型——根据模型设计状态，要求状态满足最优子结构和无后效性——直接设计状态有难度的话则需要考虑转化模型——根据设计的状态考虑转移——如果过不了题目要求的数据范围，则需要考虑优化 由于动态规划涉及的内容太多，只言片语难以讲清，所以附件中放了很多篇关于动态规划的文章，大部分系原创，并附上了一些经典的论文，主要讲了DP的优化，一些特殊的状态设计技巧 Dp和递推没有本质区别，都是用一些状态来描述问题，并记录下一些信息，根据已知信息推出未知信息，直到得到问题的解 关于DP的优化有两篇神级论文，放在附件里面了，写的非常好。 二、图论及网络流 最小生成树：克鲁斯卡尔算法和普利姆算法， ——重要性质1：最小生成树上任意两点的路径的最大边最小 ——重要性质2：最小生成树的多解（方案个数）只与相同权值的的边有关（省队集训题生成树计数） 最短路：spfa算法、堆+迪杰斯特拉算法 Spfa算法是基于松弛技术的，随机图效果极佳，最坏（网格图或存在负权环）O(nm)，适用于任意图，能够判断负权环 ——判负权环的方法：记录每个点当前从原点到它的最短路上边的条数，如果某次更新后这个条数>n-1则存在负权环 堆+迪杰斯特拉则是用了贪心的思想，不断扩大确定dist的集合，同时更新dist，如果边权有负值就不能做，复杂度是O((n+m)logn)的 拓扑排序：可以将有向图转化为一个线性的序列，满足一个点所有的前驱结点都出现在这个点在序列中的位置之前。可以判断这个有向图是否有环 ——一个简单而实用的扩展：给树做类top排序，可以有类似的功能，即每次去掉叶子结点，将树转化为一个具有拓扑关系的序列 ——再扩展：树同构判断，可用类top确定树根是谁，再最小表示法+hash即可 强连通分量、缩点：tarjan算法 核心是每个点记一个时间戳ti[i], 另外low[i]表示i点能延伸出的搜索树中节点的ti[i]的最小值，还要维护个栈记当前路径上的点，low[i]初始化为ti[i]，如果搜完i了，ti[i]=low[i]则当前栈顶到i的所有点会在一个强连同分量内。 第七章动态规划 规划问题的最终目的就是确定各决策变量的取值，以使目标函数达到极大或极小。在线性规划和非线性规划中，决策变量都是以集合的形式被一次性处理的；然而，有时我们也会面对决策变量需分期、分批处理的多阶段决策问题。所谓多阶段决策问题是指这样一类活动过程：它可以分解为若干个互相联系的阶段，在每一阶段分别对应着一组可供选取的决策集合；即构成过程的每个阶段都需要进行一次决策的决策问题。将各个阶段的决策综合起来构成一个决策序列，称为一个策略。显然，由于各个阶段选取的决策不同，对应整个过程可以有一系列不同的策略。当过程采取某个具体策略时，相应可以得到一个确定的效果，采取不同的策略，就会得到不同的效果。多阶段的决策问题，就是要在所有可能采取的策略中选取一个最优的策略，以便得到最佳的效果。动态规划（dynamic programming）同前面介绍过的各种优化方法不同，它不是一种算法，而是考察问题的一种途径。动态规划是一种求解多阶段决策问题的系统技术，可以说它横跨整个规划领域（线性规划和非线性规划）。当然，由于动态规划不是一种特定的算法，因而它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则，动态规划必须对具体问题进行具体的分析处理。在多阶段决策问题中，有些问题对阶段的划分具有明显的时序性，动态规划的“动态”二字也由此而得名。动态规划的主要创始人是美国数学家贝尔曼（Bellman）。20世纪40年代末50年代初，当时在兰德公司（Rand Corporation）从事研究工作的贝尔曼首先提出了动态规划的概念。1957年贝尔曼发表了数篇研究论文，并出版了他的第一部著作《动态规划》。该著作成为了当时唯一的进一步研究和应用动态规划的理论源泉。1961年贝尔曼出版了他的第二部著作，并于1962年同杜瑞佛思（Dreyfus）合作出版了第三部著作。在贝尔曼及其助手们致力于发展和推广这一技术的同时，其他一些学者也对动态规划的发展做出了重大的贡献，其中最值得一提的是爱尔思（Aris）和梅特顿（Mitten）。爱尔思先后于1961年和1964年出版了两部关于动态规划的著作，并于1964年同尼母霍思尔（Nemhauser）、威尔德（Wild）一道创建了处理分枝、循环性多阶段决策系统的一般性理论。梅特顿提出了许多对动态规划后来发展有着重要意义的基础性观点，并且对明晰动态规划路径的数学性质做出了巨大的贡献。 动态规划在工程技术、经济管理等社会各个领域都有着广泛的应用，并且获得了显著的效果。在经济管理方面，动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存管理问题、排序问题、设备更新问题以及生产过程最优控制问题等，是经济管理中一种重要的决策技术。许多规划问题用动态规划的方法来处理，常比线性规划或非线性规划更有效。特别是对于离散的问题，由于解析数学无法发挥作用，动态规划便成为了一种非常有用的工具。 动态规划可以按照决策过程的演变是否确定分为确定性动态规划和随机性动态规划；也可以按照决策变量的取值是否连续分为连续性动态规划和离散性动态规划。本教材主要介绍动态规划的基本概念、理论和方法，并通过典型的案例说明这些理论和方法的应用。 §7.1 动态规划的基本理论 1.1多阶段决策过程的数学描述 有这样一类活动过程，其整个过程可分为若干相互联系的阶段，每一阶段都要作出相应的决策，以使整个过程达到最佳的活动效果。任何一个阶段（stage，即决策点）都是由输入（input）、决策（decision）、状态转移律（transformation function）和输出（output）构成的，如图7-1（a）所示。其中输入和输出也称为状态（state），输入称为输入状态，输出称为输出状态。 第四章动态规划 §1 引言 1.1 动态规划的发展及研究内容 动态规划（dynamic programming）是运筹学的一个分支，是求解多阶段决策问题的最优化方法。20世纪50年代初R. E. Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优性原理（principle of optimality），把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法—动态规划。1957年出版了他的名著《Dynamic Programming》，这是该领域的第一本著作。 动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。 虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划（如线性规划、非线性规划），只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。 应指出，动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种特殊算法（如线性规划是一种算法）。因而，它不象线性规划那样有一个标准的数学表达式和明确定义的 一组规则，而必须对具体问题进行具体分析处理。因此，在学习时，除了要对基本概念和方法正确理解外，应以丰富的想象力去建立模型，用创造性的技巧去求解。 例1 最短路线问题 下面是一个线路网，连线上的数字表示两点之间的距离（或费用）。试寻求一条由A到G距离最短（或费用最省）的路线。 例2 生产计划问题 工厂生产某种产品，每单位（千件）的成本为1（千元），每次开工的固定成本为3（千元），工厂每季度的最大生产能力为6（千件）。经调查，市场对该产品的需求量第一、二、三、四季度分别为2，3，2，4（千件）。如果工厂在第一、二季度将全年的需求都生产出来，自然可以降低成本（少付固定成本费），但是对于第三、四季度才能上市的产品需付存储费，每季每千件的存储费为0.5（千元）。还规定年初和年末这种产品均无库存。试制定一个生产计划，即安排每个季度的产量，使一年的总费用（生产成本和存储费）最少。 1.2 决策过程的分类 信息学竞赛中的动态规划专题 哈尔滨工业大学周谷越 【关键字】 动态规划动机状态典型题目辅助方法优化方法 【摘要】 本文针对信息学竞赛（面向中学生的Noi以及面向大学生的ACM/ICPC）中的动态规划算法，从动机入手，讨论了动态规划的基本思想和常见应用方法。通过一些常见的经典题目来归纳动态规划的一般作法并从理论上加以分析和说明。并介绍了一些解决动态规划问题时的一些辅助技巧和优化方法。纵观全文可知，动态规划的关键在于把握本质思想的基础上灵活运用。 【目录】 1.动态规划的动机和基本思想 1.1.解决重复子问题 1.2.解决复杂贪心问题 2.动态规划状态的划分方法 2.1.一维状态划分 2.2.二维状态划分 2.3.树型状态划分 3.动态规划的辅助与优化方法 3.1.常见辅助方法 3.2.常见优化方法 4.近年来Noi动态规划题目分析 4.1 Noi2005瑰丽华尔兹 4.2 Noi2005聪聪与可可 4.3 Noi2006网络收费 4.4 Noi2006千年虫 附录参考书籍与相关材料 1.动态规划的动机和基本思想 首先声明，这里所说的动态规划的动机是从竞赛角度出发的动机。 1.1 解决重复子问题 对于很多问题，我们利用分治的思想，可以把大问题分解成若干小问题，然后再把各个小问题的答案组合起来，得到大问题的解答。这类问题的共同点是小问题和大问题的本质相同。很多分治法可以解决的问题（如quick_sort，hanoi_tower等）都是把大问题化成2个以内的不相重复的小问题，解决的问题数量即为∑(log2n / k)。而考虑下面这个问题： USACO 1.4.3 Number Triangles http://122.139.62.222/problem.php?id=1417 【题目描述】 考虑在下面被显示的数字金字塔。 写一个程序来计算从最高点开始在底部任意处结束的路径经过数字的和的最大。每一步可以走到左下方的点也可以到达右下方的点。 7 3 8 8 1 0 2 7 4 4 4 5 2 6 1 在上面的样例中，从7到3到8到7到5的路径产生了最大和：30。 【输入格式】 第一个行包含R(1<= R<=1000) ,表示行的数目。后面每行为这个数字金字塔特定行包含的整数。所有的被供应的整数是非负的且不大于100。 【输出格式】 单独的一行包含那个可能得到的最大的和。 【样例输入】 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 1 【样例输出】 30 显然，我们同样可以把大问题化成小问题来解决。如样例中最底层的6就可以从次底层 1、单调递增最长子序列 描述 求一个字符串的最长递增子序列的长度 如：dabdbf最长递增子序列就是abdf，长度为4 输入 第一行一个整数0 2、最长公共子序列 描述 如题，需要写一个程序，得出最长公共子序列。 tip：最长公共子序列也称作最长公共子串(不要求连续)，英文缩写为LCS（Longest Common Subsequence）。其定义是，一个序列S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则S 称为已知序列的最长公共子序列。 输入 第一行给出一个整数N(0 3、括号匹配 时间限制：1000 ms | 内存限制：65535 KB 描述 给你一个字符串，里面只包含"(",")","[","]"四种符号，请问你需要至少添加多少个括号才能使这些括号匹配起来。 如： []是匹配的 ([])[]是匹配的 ((]是不匹配的 ([)]是不匹配的 输入 第一行输入一个正整数N，表示测试数据组数(N<=10) 每组测试数据都只有一行，是一个字符串S，S中只包含以上所说的四种字符， S的长度不超过100 输出 对于每组测试数据都输出一个正整数，表示最少需要添加的括号的数量。每组 测试输出占一行 样例输入 4 [] ([])[] ((] ([)] 样例输出 3 2 动态规划习题 Document serial number【NL89WT-NY98YT-NC8CB-NNUUT-NUT108】 动态规划专题分类视图数轴动规题： 题1.2001年普及组第4题--装箱问题 【问题描述】有一个箱子容量为V(正整数,0≤V≤20000),同时有n个物品(0 对于100%的数据,砝码的种类n满足:1≤n≤100; 对于30%的数据,砝码的总数量C满足:1≤C≤20; 对于100%的数据,砝码的总数量C满足:1≤C≤100; 对于所有的数据,砝码的总重量W满足:1≤W≤400000; 题3.石子归并-szgb.pas 【问题描述】有一堆石头质量分别为W1,W2,…,Wn.(Wi≤10000),将石头合并为两堆,使两堆质量的差最小。 【输入】输入文件szgb.in的第一行只有一个整数n(1≤n≤50),表示有n堆石子。接下去的n行,为每堆石子质量。 【输出】输出文件szgb.out的只有一行,该行只有一个整数,表示最小的质量差. 【样例输入】 5 5 8 13 27 14 【样例输出】 3 题4.补圣衣 【问题描述】有四个人，每人身上的衣服分别有s1,s2,s3和s4处破损,而且每处破损程度不同,破损程度用需修好它用的时间表示 (A1...As1,B1...Bs2,C1...Cs3,D1...Ds4)。不过你可以同时修补2处破损。但是这2处破损，只能是同一件衣服上的。就是说你只能同时修补一件衣服，修好了，才能修补下一件。 【输入】本题包含5行数据：第1行，为s1,s2,s3,s4(1≤s1,s2,s3,s4≤20) 第2行，为A1...As1共s1个数，表示第一件衣服上每个破损修好它所需的时间 第3行，为B1...Bs2共s2个数，表示第二件衣服上每个破损修好它所需的时间 第4行，为C1...Cs3共s3个数，表示第三件衣服上每个破损修好它所需的时间 第5行，为D1...Ds4共s4个数，表示第四件衣服上每个破损修好它所需的时间 (1≤A1...As1,B1...Bs2,C1...Cs3,D1...Ds4≤60) 【输出】输出一行,为修好四件衣服所要的最短时间。 【样例输入】 1213 5 43 6 243 【样例输出】 20 题5.光光的作业homework.pas/homework.exe 【问题描述】光光上了高中，科目增多了。在长假里，光光的老师们都非常严厉，都给他布置了一定量的作业。假期里，光光一共有的时间是k小时。在长假前，老师们一共给光光布置了n份作业，第i份作业需要的时间是ti小时。但是由于老师们互相不 NOIP2017提高组初赛试题及答案 一、单项选择题（共15 题，每题1.5 分，共计22.5 分；每题有且仅有一个正确选项） 1. 从( )年开始，NOIP 竞赛将不再支持Pascal 语言。C A. 2020 B. 2021 C. 2022 D. 2023 2.在8 位二进制补码中，10101011 表示的数是十进制下的( )。B A. 43 B. -85 C. -43 D.-84 3.分辨率为1600x900、16 位色的位图，存储图像信息所需的空间为( )。A A. 2812.5KB B. 4218.75KB C. 4320KB D. 2880KB 4. 2017年10月1日是星期日，1949年10月1日是( )。C A. 星期三 B. 星期日 C. 星期六 D. 星期二 5. 设G 是有n 个结点、m 条边(n ≤m)的连通图，必须删去G 的( )条边，才能使得G 变成一棵树。A A.m–n+1 B. m-n C. m+n+1 D.n–m+1 6. 若某算法的计算时间表示为递推关系式：T(N)=2T(N/2)+NlogN T(1)=1 则该算法的时间复杂度为( )。C A.O(N) B.O(NlogN) C.O(N log2N) D.O(N2) 7. 表达式a * (b + c) * d的后缀形式是()。B A. abcd*+* B. abc+*d* C. a*bc+*d D. b+c*a*d 8. 由四个不同的点构成的简单无向连通图的个数是( )。C A. 32 B. 35 C. 38D. 41 9. 将7个名额分给4个不同的班级，允许有的班级没有名额，有( )种不同的分配方案。D A. 60 B. 84 C. 96 D.120 10. 若f[0]=0, f[1]=1, f[n+1]=(f[n]+f[n-1])/2，则随着i的增大，f[i]将接近与( )。B A. 1/2 B. 2/3 D. 1 11. 设A和B是两个长为n的有序数组，现在需要将A和B合并成一个排好序的数组，请问任何以元素比较作为基本运算的归并算法最坏情况下至少要做( )次比较。D A. n2 B. Nlogn C. 2n D.2n-1 12. 在n(n>=3)枚硬币中有一枚质量不合格的硬币（质量过轻或质量过重），如果只有一架天平可以用来称重且称重的硬币数没有限制，下面是找出这枚不合格的硬币的算法。请把a-c三行代码补全到算法中。 2. 将A中硬币分成X,Y,Z三个集合，使得|X|=|Y|=k, |Z|=n-2k 3. if W(X)≠W(Y) //W(X), W(Y)分别为X或Y的重量 4. then_______ 5. else_______ 6. __________ 7. if n>2 then goto 1 8. if n=2 then 任取A中1枚硬币与拿走硬币比较，若不等，则它不合格；若相等，则A中剩下的硬币不合格 9. if n=1 then A中硬币不合格 正确的填空顺序是( )。D A. b,c,a B. c,b,a C. c,a,b D.a,b,c 13. 在正实数构成的数字三角形排列形式如图所示，第一行的数为a11；第二行的数从左到右依次为a21,a22;…第n行的数为 an1,an2,…，ann。从a11开始，每一行的数aij只有两条边可以分别通向下一行的两个数a(i+1)j和a(i+1)(j+1)。用动态规划算法找出一条从a11向下通到an1,an2,…,ann中某个数的路径，使得该路径上的数之和达到最大。 令C[i,j]是从a11到aij的路径上的数的最大和，并且C[i,0]=C[0,j]=0，则C[i,j]=( )。A A. max{C[i-1,j-1],C[i-1,j]}+aij B. C[i-1,j-1]+c[i-1,j] C. max{C[i-1,j-1],C[i-1,j]}+1 D. max{C[i,j-1],C[i-1,j]}+aij 14. 小明要去南美洲旅游，一共乘坐三趟航班才能到达目的地，其中第1个航班准点的概率是0.9，第2个航班准点的概率为0.8，第3个航班准点的概率为0.9。如果存在第i个（i=1,2）航班晚点，第i+1个航班准点，则小明将赶不上第i+1个航班，旅行失败；除了这种情况，其他情况下旅行都能成功。请问小明此次旅行成功的概率是( )。D 动态规划的优化一、时间上的优化 花店橱窗布置问题（IOI99试题）。假设想以最美观的方式布置花店的橱窗，有F束花，每束花的品种都不一样，同时，至少有同样数量的花瓶，被按顺序摆成一行，花瓶的位置是固定的，并从左到右，从1到V顺序编号，V是花瓶的数目，编号为1的花瓶在最左边，编号为V的花瓶在最右边，花束可以移动，并且每束花用1到F的整数唯一标识，标识花束的整数决定了花束在花瓶中列的顺序，即如果I＜J，则花束I必须放在花束J左边的花瓶中。例如，假设杜鹃花的标识数为1，秋海棠的标识数为2，康乃馨的标识数为3，所有的花束在放入花瓶时必须保持其标识数的顺序，即：杜鹃花必须放在秋海棠左边的花瓶中，秋海棠必须放在康乃馨左边的花瓶中。如果花瓶的数目大于花束的数目,则多余的花瓶必须空，即每个花瓶中只能放一束花。 每一个花瓶的形状和颜色也不相同，因此，当各个花瓶中放入不同的花束时，会产生不同的美学效果，并以美学值（一个整数）来表示，空置花瓶的美学值为0。在上述例子中，花瓶与花束的不同搭配所具有的美学值，可以用如下表格表示： 根据表格，杜鹃花放在花瓶2中，会显得非常好看，但若放在花瓶4中则显得很难看。 为取得最佳美学效果，必须在保持花束顺序的前提下，使花的摆放取得最大的美学值，如果具有最大美学值的摆放方式不止一种，则输出任何一种方案即可。题中数据满足下面条件：1≤F≤100，F≤V ≤100，－50≤A IJ≤50，其中A IJ是花束I摆放在花瓶J中的美学值。输入整数F，V和矩阵（A IJ），输出最大美学值和每束花摆放在各个花瓶中的花瓶编号。 【分析】问题实际就是给定F束花和V个花瓶，以及各束花放到不同花瓶中的美学值，需要你找出一种摆放的方案，使得在满足编号小的花放进编号小的花瓶中的条件下，美学值达到最大。 （1）将问题进行转化，找出问题的原型。首先，看一下上述题目的样例数据表格。 将摆放方案的要求用表格表现出来，则摆放方案需要满足：每行选且只选一个数（花瓶）；摆放方案的相邻两行中，下面一行的花瓶编号要大于上面一行的花瓶编号两个条件。这时可将问题转化为：给定一个数字表格，要求编程计算从顶行至底行的一条路径，使得这条路径所经过的数字总和最大（要求每行选且仅选一个数字）。同时，路径中相邻两行的数字，必须保证下一行数字的列数大于上一行数字的列数。 动态规划练习题 [题1] 多米诺骨牌（DOMINO） 问题描述：有一种多米诺骨牌是平面的，其正面被分成上下两部分，每一部分的表面或者为空，或者被标上1至6个点。现有一行排列在桌面上：顶行骨牌的点数之和为6+1+1+1=9；底行骨牌点数之和为1+5+3+2=11。顶行和底行的差值是2。这个差值是两行点数之和的差的绝对值。每个多米诺骨牌都可以上下倒置转换，即上部变为下部，下部变为上部。 现在的任务是，以最少的翻转次数，使得顶行和底行之间的差值最小。对于上面这个例子，我们只需翻转最后一个骨牌，就可以使得顶行和底行的差值为0，所以例子的答案为1。 输入格式： 文件的第一行是一个整数n（1〈=n〈=1000〉，表示有n个多米诺骨牌在桌面上排成一行。接下来共有n行，每行包含两个整数a、b（0〈=a、b〈=6，中间用空格分开〉。第I+1行的a、b分别表示第I个多米诺骨牌的上部与下部的点数（0表示空）。 输出格式： 只有一个整数在文件的第一行。这个整数表示翻动骨牌的最少次数，从而使得顶行和底行的差值最小。 [题2] Perform巡回演出 题目描述: Flute市的Phlharmoniker乐团2000年准备到Harp市做一次大型演出,本着普及古典音乐的目的,乐团指挥L.Y.M准备在到达Harp市之前先在周围一些小城市作一段时间的巡回演出,此后的几天里,音乐家们将每天搭乘一个航班从一个城市飞到另一个城市,最后才到达目的地Harp市(乐团可多次在同一城市演出). 由于航线的费用和班次每天都在变,城市和城市之间都有一份循环的航班表,每一时间,每一方向,航班表循环的周期都可能不同.现要求寻找一张花费费用最小的演出表. 输入: 输入文件包括若干个场景.每个场景的描述由一对整数n(2<=n<=10)和k(1<=k<=1000)开始,音乐家们要在这n个城市作巡回演出,城市用1..n标号,其中1是起点Flute市,n是终点Harp市,接下来有n*(n-1)份航班表,一份航班表一行,描述每对城市之间的航线和价格,第一组n-1份航班表对应从城市1到其他城市(2,3,...n)的航班,接下的n-1行是从城市2到其他城市(1,3,4...n)的航班,如此下去. 每份航班又一个整数d(1<=d<=30)开始,表示航班表循环的周期,接下来的d 个非负整数表示1,2...d天对应的两个城市的航班的价格,价格为零表示那天两个城市之间没有航班.例如"3 75 0 80"表示第一天机票价格是75KOI,第二天没 Noip常用算法大全 一、数论算法 1．求两数的最大公约数 function gcd(a,b:integer):integer; begin if b=0 then gcd:=a else gcd:=gcd (b.a mod b); end ; 2．求两数的最小公倍数 function lcm(a,b:integer):integer; begin if a0 do inc(lcm,a); end; 3．素数的求法 A.小范围内判断一个数是否为质数： function prime (n: integer): Boolean; var I: integer; begin for I:=2 to trunc(sqrt(n)) do if n mod I=0 then begin prime:=false; exit; end; prime:=true; end; B.判断longint范围内的数是否为素数（包含求50000以内的素数表）： procedure getprime; var i,j:longint; p:array[1..50000] of boolean; begin fillchar(p,sizeof(p),true); p[1]:=false; i:=2; while i<50000 do begin if p[i] then begin j:=i*2; while j<50000 do begin {筛选法} p[j]:=false; inc(j,i); end; end; inc(i); end; l:=0; for i:=1 to 50000 do if p[i] then begin inc(l);pr[l]:=i; end; end;{getprime} function prime(x:longint):boolean; var i:integer; begin prime:=false; for i:=1 to l do if pr[i]>=x then break else if x mod pr[i]=0 then exit; prime:=true; end;{prime} 二、图论算法 1．最小生成树 A.Prim算法： procedure prim(v0:integer); var lowcost,closest:array[1..maxn] of integer; i,j,k,min:integer; begin for i:=1 to n do begin lowcost:=cost[v0,i]; closest:=v0; end; for i:=1 to n-1 do begin {寻找离生成树最近的未加入顶点k} min:=maxlongint; for j:=1 to n do if (lowcost[j] 顺序对齐 源程序名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个任务单独完成所需的时间是T i。在每批任务开始前，机器需要启动时间S，而完成这批任务所需的时间是各个任务需要时间的总和（同一批任务将在同一时刻完成）。每个任务的费用是它的完成时刻乘以一个费用系数F i。请确定一个分组方案，使得总费用最小。 动态规划专题分类视图 数轴动规题： (1) 较复杂的数轴动规 (4) 线性动规 (7) 区域动规： (14) 未知的动规： (20) 数轴动规题： 题1.2001年普及组第4题--装箱问题 【问题描述】有一个箱子容量为V(正整数,0≤V≤20000),同时有n个物品(0 的个数，但不包括一个砝码也不用的情况。 【输入格式】输入文件weight.in的第一行只有一个数n,表示不同的砝码的种类数. 第2行至第n+1行,每行有两个整数.第k+1行的两个数分别表示第k种砝码的个数和重量. 【输出格式】输出文件weight.out中只有一行数据:Total=N。表示用这些砝码能秤出的不同重量数。【输入样例】 2 2 2 2 3 【输出样例】 Total=8 【样例说明】 重量2,3,4,5,6,7,8,10都能秤得 【数据限制】 对于100%的数据,砝码的种类n满足:1≤n≤100; 对于30%的数据,砝码的总数量C满足:1≤C≤20; 对于100%的数据,砝码的总数量C满足:1≤C≤100; 对于所有的数据,砝码的总重量W满足:1≤W≤400000; 题3.石子归并-szgb.pas 【问题描述】有一堆石头质量分别为W1,W2,…,Wn.(Wi≤10000),将石头合并为两堆,使两堆质量的差最小。 【输入】输入文件szgb.in的第一行只有一个整数n(1≤n≤50),表示有n堆石子。接下去的n行,为每堆石子质量。 【输出】输出文件szgb.out的只有一行,该行只有一个整数,表示最小的质量差. 【样例输入】 5 5 8 13 27 14 【样例输出】 3 题4.补圣衣 【问题描述】有四个人，每人身上的衣服分别有s1,s2,s3和s4处破损,而且每处破损程度不同,破损程度用需修好它用的时间表示(A1...As1,B1...Bs2,C1...Cs3,D1...Ds4)。不过你可以同时修补2处破损。但是这2处破损，只能是同一件衣服上的。就是说你只能同时修补一件衣服，修好了，才能修补下一件。【输入】本题包含5行数据：第1行，为s1,s2,s3,s4(1≤s1,s2,s3,s4≤20) 第2行，为A1...As1 共s1个数，表示第一件衣服上每个破损修好它所需的时间 第3行，为B1...Bs2 共s2个数，表示第二件衣服上每个破损修好它所需的时间 第4行，为C1...Cs3 共s3个数，表示第三件衣服上每个破损修好它所需的时间 第5行，为D1...Ds4 共s4个数，表示第四件衣服上每个破损修好它所需的时间 (1≤A1...As1,B1...Bs2,C1...Cs3,D1...Ds4≤60)动态规划例题
动态规划问题整理
动态规划讲解大全(含例题及答案)
NOIP 2017全国青少年信息学奥林匹克联赛提高组初赛试题答案
noip算法总结2016
动态规划习题
(整理)matlab 动态规划讲义.
动态规划习题精讲
动态规划典型例题
动态规划习题完整版
NOIP2017提高组初赛试题及答案
动态规划的优化讲义
动态规划练习试题和解答1
Noip常用算法大全
动态规划：NOIP的题目
动态规划习题
相关主题
文本预览