枚举、搜索与动态规划试题精讲.ppt_第1页
枚举、搜索与动态规划试题精讲.ppt_第2页
枚举、搜索与动态规划试题精讲.ppt_第3页
枚举、搜索与动态规划试题精讲.ppt_第4页
枚举、搜索与动态规划试题精讲.ppt_第5页
已阅读5页,还剩78页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

枚举、搜索与动态规划 试 题 精 讲,朱全民,枚举,所谓枚举法,指的是从可能的解集合中一一枚举各元素,用题目给定的检验条件判定哪些是无用的,哪些是有用的.能使命题成立,即为其解。一般思路: 对命题建立正确的数学模型; 根据命题确定的数学模型中各变量的变化范围(即可能解的范围); 利用循环语句、条件判断语句逐步求解或证明; 枚举法的特点是算法简单,但有时运算量大。对于可能确定解的值域又一时找不到其他更好的算法时可以采用枚举法。,枚举法求解的问题必须满足两个条件: 可预先确定每个状态的元素个数n; 状态元素a1,a2,an的可能值为一个连续的值域。 设ai1状态元素ai的最小值;aik状态元素ai的最大值(1in)即a11a1a1k , a21a2a2k ,ai1aiaik , , an1anank for a1a11 to a1k do fo a2a21 to a2k do for anan1 to ank do if 状态(a1,ai,an)满足检验条件 then 输出问题的解;,枚举算法的优化 枚举算法的时间复杂度可以用状态总数*考察单个状态的耗时来表示,因此优化主要是 减少状态总数(即减少枚举变量和枚举变量的值域) 降低单个状态的考察代价 优化过程从几个方面考虑。具体讲 提取有效信息 减少重复计算 将原问题化为更小的问题 根据问题的性质进行截枝 引进其他算法,侦探推理 (NOIP2003-2),证词中出现的其他话,都不列入逻辑推理的内容。 明明所知道的是,他的同学中有N个人始终说假话,其余的人始终说真话。 现在,明明需要你帮助他从他同学的话中推断出谁是真正的凶手,请记住,凶手只有一个! 要求: 判断谁是罪犯?,分析,这道题的关键点是“如何能够快速正确实现出来” ,事实上这道题对编码能力的要求要大于对算法本身的要求。由于这道题的数据范围并不是很大,但需要进行“字符串处理”这种比较麻烦的工作,因此在比赛时就可以采用效率低一些的枚举算法来换取编码上的简单。 推荐的算法分为两步: 1预处理每个人的每一句话,并把它们分类处理; 2枚举罪犯和当前星期几,找出所有可能发生的情况。 下面我们来逐步细化一下每一步的算法,对于第一步,我们希望的是把一些杂乱的不好处理的“字符串信息”转化为相对比较好处理的信息。为此,我们可以通过把“信息”进行分类的方法使得对于每一类信息,更加方便的处理(即我们可以用一个或者几个变量来表示),由题目描述可以发现语句可分为三类:,分析,1指明i是否是罪犯的语句; 2指明今天是星期d的语句; 3没有意义的语句(不符合格式要求)。 我们必须要说明的是任何不符合格式要求的语句都将被划分到第三类中去,这样在处理每个语句的时候就必须要考虑该语句是否符合格式要求,通过以上的处理,我们对于每一个语句用几个变量就可以表示了。 对于第二步的细化,我们在枚举完罪犯和当前星期几之后,就可以比较方便的判断每一句话的真伪了,这样我们再根据每个人所说的话把人进行分类。 1没说任何一句有意义的话; 2只说真话; 3只说假话; 4既说真话也说假话。,分析,需要注意的是,对于第一类人我们既可以把他当成说真话的,也可以把他当成说假话的,而如果第四类人存在的话,那么从他本身就可以推出矛盾了。 最后,如果对于罪犯i存在一个d使得当前情况是可能的,我们就说i就是可能的罪犯。 时间效率 O(MP|Day|) (其中Day=Sunday,Monday, Tuesday, Wednesday, Thursday, Friday, Saturday),优化,我们可以发现在对罪犯和当前星期几进行“双重枚举”时,进行了很多重复的操作,于是我们想到,能不能不枚举是当前星期几?这样我们把这类语句与判断罪犯的语句分离,可以先由判断罪犯的语句中确定一部分人肯定说真话,一部分人肯定说假话,剩下的一部分人就要根据他所说的当前星期几的语句来判断了,首先我们假设所有人判断星期的语句不自相矛盾,这样每个人将在判断这类问题里面至多有一个答案,我们便可以统计判断当前是星期d的总人数,于是改进后的算法对于每一个可能的罪犯,先用O(p)的时间处理所有的话,再用O(|Day|)的时间枚举星期几。这样,改进后算法的复杂度就是O(m(p+|Day|)。 那么我们可不可以再进一步,把算法优化到线性?这里面可以比较明确地告诉大家,是可以做到的,具体的算法类似于上面的按照语句的种类分离语句,只是分离得更细,处理得更复杂,在这里就不做赘述,留给大家思考。,现有一个棱长为n的立方体,可以分成n3个1*1*1的单位立方体。每个单位立方体都有一个整数值。n3个单位立方体的数和不会超过longint范围。现在要求在这个立方体找到一个包含完整单位立方体的长方体,使得该长方体内所有单位立方体的数和最大。 输入: n(1n20);n个n*n的数字矩阵,每个数字矩阵代表一层,每个数字代表一个单位立方体的整数值,-999单位立方体的整数值999 输出:长方体的数和 1、“直译”枚举过程 for x11 to n do 枚举所有可能的平面 for x21 to n do for y11 to n do for y21 to n do for z11 to n do 枚举所有可能的上平面和下底面 for z21 to n do 考察状态(x1,y1,z1,x2,y2,z2);,立方体问题,考察状态(x1,y1,z1,x2,y2,z2)的任务是计算长方体的体积,并调整最优解。设map为立方体对应的三维矩阵;sum为当前长方体的体积;best为最优解。考察过程如下 sum0; for xx1 to x2 do 计算长方体的体积 for yy1 to y2 do for zz1 to z2 do sumsum+mapx,y,z; 调整最优解 if sumbest then bestsum; 这个算法相当粗糙,枚举状态的费用为O(n9) 2、从减少重复计算入手 记录先前考察的结果。在统计长方体2时,只要将长方体1的统计结果加上长方体3就可以了,而不必按上述算法那样重新进行计算。,for x11 to n do 枚举所有可能的水平面 for x21 to n do for y11 to n do for y21 to n do for z11 to n do 枚举上平面的z轴坐标 begin sum0; 长方体的体积初始化 for z21 to n do 枚举下底面的z轴坐标 考察状态(x1,y1,z1,x2,y2,z2); end;for 考察过程改为 for xx1 to x2 do 计算长方体的体积 for yy1 to y2 do sumsum+mapx,y,z2; if sumbest then bestsum; 调整最优解 由于利用了计算出的结果,整个算法的时间复杂度降为O(n8)。,3、提取恰当的信息 上述考察实际上求出z轴坐标为z2的平面中矩形(x1,y1,x2,y2)的数和。我们将这个数和记为value(a) value(A)=value(ABCD)+value(B)-value(BC)-value(BD) 这就启发我们用另一种方法表示立方体的信息:设recx,y,z表示z轴坐标为z的水平面中矩形(1,1,x,y)的数和。 z轴坐标为z的水平面中左上角为(x1,y1)、右下角为(x2,y2)的矩阵的数和为recx2,y2,z+ recx1,y1,z-recx2,y1,z-recx1,y2,z,Rec数组可以在输入数据的同时计算 fillchar(rec,size(rec),0);rec数组初始化 for z1 to n do 逐层输入信息 for x1 to n do 逐行输入z平面的信息 begin for y1 to n do 逐列输入z平面上x行的信息 begin read(mapx,y,z); 输入z平面上(x,y)中的数 if (x=1)and(y=1) 计算z平面上以(1,1)为左上角、(x,y)为右下角的矩形的数和 then rec1,1,zmap1,1,z else if y=1 then recx,y,zrecx-1,n,z+mapx,y,z else recx,y,zrecx,y-1,z+mapx,y,z; end;for readln; end;for 这样,考察过程就可以改为 sumsum+recx2,y2,z2+recx1,y1,z2-recx2,y1,z2-recx1,y2,z2; if sumbest then bestsum; 时间复杂度降为O(n6)。,如果长方体a的数和是负数,则长方体a的计算结果废弃,考察长方体b-a。因为长方体b的数和=长方体b-a的数和+长方体a的数和,由于长方体a的数和为负,长方体b-a的数和一定大于等于长方体b的数和。由此可见,在累计长方体数和的时候,只要由上而下地枚举长方体下底面的z轴坐标即可。设 total(z)以z轴坐标为z的平面为下底面的长方体的最大数和,for x11 to n do 枚举所有可能的子平面 for x21 to n do for y11 to n do for y21 to n do begin total0;长方体以(x1,y1)为左上角,(x2,y2)为右下角)的最大数和初始化 for z1 to n do 枚举长方体b下底面的z轴坐标 begin totalmaxtotal,0+ recx2,y2,z+ recx1-1,y1-1,z-recx2,y1-1,z-recx-1-1,y2,z; 计算以z为下底面的长方体b的最大数和 if total best then besttotal; 调整最优解 end;for end;for 这一改进使得考察的状态整数降为O(n5),子串,给定一个由自然数串联而成的无限数列1234567891011121314(母串) 求任意一个长度不超过200的数列(子串)在其中最早出现的位置。,分析:,首先,由于母串可无限扩充,显然我们不可能把它全部生成出来。 如果边生成母串,边判断所生成的数串是否包含给定的子串,即使是使用字符串处理中高效的KMP算法,耗费的工作量也是巨大的。,1121314,先枚举第1位1 自然数1之后为2,3, 母串中形如123 与子串从第2位开始不符,枚举前2位11 自然数11之后为12,13 母串中形如111213 与子串从第3位开始不符,考虑第2位开始12 自然数12之前为11,末位与子串第1位相同,之后为13,14, 母串中形如1314 与子串匹配!,如何优化呢?,较好的方法是另辟蹊径: 刚才我们枚举的是母串的每一位,不妨换一个角度,从子串着手。 先来观察一些片断: 12345678910111213141516,很自然得到算法:,枚举子串所包含第一个完整的数a的位数La。 假设a在母串的第k位出现(kAns_k 4跟据Ans_a及Ans_k计算出位数,总时间复杂度约为O(n3),与之前的不可估量相比有了本质性提高。 第4步可通过多种途径求得,这里不作介绍。 由于其中牵涉到许多高精度的计算及字符串处理,要求我们细致认真。,小结,充分挖掘题目特性是解决本题的关键。 得以使枚举这类看似低效率的方法得到较好的运用。 同时细致全面的考虑问题也是必不可少的。,宽度优先遍历算法框架,从某个未被访问的顶点v出发,依次访问v的各个未曾访问过的邻接点.然后分别从这些邻接点出发广度优先搜索遍历,直到所有已被访问的邻接点都被访问到. PROC bfs(v); Visite(v); vistedv:=true; Iniqueue(q); enqueue(q,v); While not empty(q) do v:=dlqueue(q); w:=FIRSTADJ(v); While w0 do if not visitedw then visite(w);visitedw:=true; enqueue(q,w) w:=NEXTADJ(v,w); ENDP,神经网络(NOIP2003-1),在兰兰的模型中,神经网络就是一张有向图,图中的节点称为神经元,而且两个神经元之间至多有一条边相连,下图是一个神经元的例子:,图中,X1X3是信息输入渠道,Y1Y2是信息输出渠道,C1表示神经元目前的状态,Ui是阈值,可视为神经元的一个内在参数。 神经元按一定的顺序排列,构成整个神经网络。在兰兰的模型之中,神经网络中的神经无分为几层;称为输入层、输出层,和若干个中间层。每层神经元只向下一层的神经元输出信息,只从上一层神经元接受信息。,神经网络,兰兰规定,Ci服从公式:(其中n是网络中所有神经元的数目),公式中的Wji(可能为负值)表示连接j号神经元和 i号神经元的边的权值。当 Ci大于0时,该神经元处于兴奋状态,否则就处于平静状态。当神经元处于兴奋状态时,下一秒它会向其他神经元传送信号,信号的强度为Ci。 如此在输入层神经元被激发之后,整个网络系统就在信息传输的推动下进行运作。现在,给定一个神经网络,及当前输入层神经元的状态(Ci),要求你的程序运算出最后网络输出层的状态。 【输入格式】 第一行是两个整数n(1n20)和p。接下来n行,每行两个整数,第i1行是神经元i最初状态和其阈值(Ui),非输入层的神经元开始时状态必然为0。再下面P行,每行由两个整数i,j及一个整数Wij,表示连接神经元i、j的边权值为Wij。 【输出格式】 输出包含若干行,每行有两个整数,分别对应一个神经元的编号,及其最后的状态,两个整数间以空格分隔。仅输出最后状态非零的输出层神经元状态,并且按照编号由小到大顺序输出! 若输出层的神经元最后状态均为 0,则输出 NULL。,分析,理解问题的第一步就是认真“读题”。那么我们先来看一看这个题目涉及的问题。研究一下题目中所给的图的一些性质,可以发现如下特点: 1图中所有的节点都有一个确定的等级,我们记作Level(i) 2图中所有的边都是有向的,并且从Level值为i-1的节点指向Level值为i的节点 我们不妨将其抽象为“阶段图”。 更一般地,我们可以发现所有的阶段图都是有向无环的,这样我们可以通过拓扑排序来得到期望的处理节点的顺序。,可行算法,由于阶段图的性质使得该图的所有边所连接节点的等级都是相邻的,因此就可以设计出一个基于宽度优先搜索(即BFS)的算法: 1初始时将所有输入层的节点放入队列; 2取出队列中的一个元素,不重复地扩展并处理该节点所发出的边的目标节点; 3如果队列非空,则转向2; 4输出输出层中所有满足条件的节点。 但是由于本题在问题描述中并没有明确的给出判断一个节点是否是输入节点,因此需要在算法进行的过程当中额外地考虑一些边界情况的数据(这个过程即便是真实数据没有这样出也是要有的),下面给出的更一般的算法可能会更好的跳过这些边界情况。 1对原图中所有的节点进行一次拓扑排序; 2按照拓扑顺序处理每一个节点; 3输出输出层中所有满足条件的节点。,Amazing Robots: IOI2003,已知条件: 迷宫 i(i=1,2) (每个不会大于20*20) 守卫 Gi(0=Gi=10) (守卫循环移动进行执勤) (守卫巡逻的方格数(24) 求: 两个机器人都离开迷宫所用的最少指令数目 和离开制指令序列(10000 步以内)。,每一步可以发出的命令可以是N, E, S, W中的一种,有4种选择。 对每一步具体发出哪个命令,直接搜索。 假设最后结果是T。(也就是最少出宫时间) 时间复杂度是O(4T),这种方法时间复杂度太高,绝对不可行!,5*4和4*4的迷宫 第一个机器人的位置是(2,2) 第二个机器人的位置是(3,2) 当前时间是0。 状态(2,2),(3,2),0),状态表示: (第一个机器人位置,第二个机器认位置,时间),E,(2,2),(3,2),0),(2,3),(3,3),1),时间已知,则所有Guard的位置可知。 Guard、Robot的位置均已知,所以状态可以转移,0时刻,1时刻,2时刻,3时刻,0时刻和2时刻是一样的 1时刻和3时刻是一样的。 稍加分析:此Guard循环以2为周期循环。,状态转移,需要的信息是:Robot位置,Guard位置。 Position of Robot1, 2是的作用就是记录Robot位置。 Time的作用就是为了计算Guard的位置,状态:(position of Robot1, position of Robot2, Time) Time=10000,这是状态数过多的罪魁祸首!,题目说:Guard巡逻经过的格子数只可能是2, 3, 4。 也就是说机器人巡逻周期只能是2, 4, 6。 2, 4, 6=12,所以第0时刻、12时刻、24时刻Guard的状态完全相同。 12可以看作Guard的周期。Time只要记录当前是第几个周期。因为周期确定了,Guard的位置也完全确定了!,0=Time=11,状态数(n*n)*(n*n)*12=12n4。 用BFS算法,标志数组判重。 时间复杂度O(12n4)。,n=20 完全可以承受 -,深度优先遍历,从某个未被访问的顶点v出发,深度优先遍历图,直到和v有路径的顶点都访问到. PROC dfs(v); visite(v);visitedv=true; w:=FIRSTADJ(v); while w0 do if not visitedw then dfs(w) w:=NEXTADJ(v,w); ENDP,讨论:虫食算问题,给出一个N进制的虫食算式,相同的字母代表相同的数字,不同的字母代表不同的数字。要求求出满足这个算式的唯一一组解,也就是字母和数字的一一对应关系.,解决方案1:,要求一一对应的关系,就可以枚举这些一一对应的关系,找出符合的一项。这样,关系总数有O(N!)个,最坏情况下必须枚举所有的关系,并且加以判断,复杂度高达O(N*N!)!,解决方案2: 大体上,从算式最后一位开始模拟运算情况,当可递推时递推,不可递推则枚举。 对于一竖列,先处理两个加数,当遇到的字母的值不确定时,则枚举当前位(注意与前面的情况判重);否则不作为处理和,当遇到的字母的值不确定时,可从加数部分确定的值来确定(注意与前面的情况判重和进位);否则看加数部分确定的值是否能得到和部分(注意进位)。引出矛盾就回溯。 如题目的样例: 5 ABCED BDACE EBBAA 它最后一位的情况是(D+E) mod N=A, 对于最后一位只要枚举D,E的情况;A 则可以由D,E的值递推而来。对于倒2位, (E+C+最后一位进位) mod N=A ;E的值可以用前面的结果;枚举C;判断A是否为(D+C+最后一位进位) mod N 虽然复杂度还是O(N!),但这种方法限制很多(相当于剪枝)。,解决方案3: 观察题目的条件已经限制得很苛刻:N个变量,每个至少出现一次;而且正好一共有N位的算式。这样就构成了解方程的动机。这N个变量的对应N个未知量,有N位的算式对应N个方程;N个未知量,N个方程,正好可以得到唯一解。这里要注意,对解的要求很严格:必须是0至N-1的每个整数都正好出现一次。 但对每位式子的进位关系并不清楚,而进位关系正好影响了方程的常数项。枚举每位是否进位。用时O(2n), (因为首位不可能进位,无须枚举)。然后,用高斯消元法来解方程。可以在枚举之前先解出方程,枚举的时候再把参数带入。带入求解的复杂度是O(n2) 。,解决方案4: 在解决方案3的基础上,我们可以对进位的枚举剪枝。观察这个竖列:A+B=C,若无进位则有AC且B=C. 若能推导出A=A (A,B为任何不相等字母),则当前的枚举不可行。可用递归枚举,从后向前枚举,处理一个竖列时则加上2个不等式,看是否矛盾。数据结构用邻接矩阵。(规定A)。 若加进不等式A=B ,要加入所有x(x=A) =y(B=y),枚举x,y用O(n2)得时间。再判断是否有x=y.,森林中的果树,森林中长着一种奇怪的果树,在每个分叉处生长着果实,小虫Nileh和Nixed的食物就是这些果实!他们准备把果树分成两部分,每个虫虫得到各自的一部分,而分果树的方法就是选择一个分叉点,虫虫将他们咬断(自然分叉点上的果实也被扔掉了),这样果树就变成了两个部分:分叉点上面的部分和分叉点下面的部分。 (注意,每个部分不一定是连在一起的),比如对于右边这颗果树,如果他们咬掉蓝色的果子,那么就被分为红色和黄色的两个部分。 被咬掉的果子会被浪费,他们想尽可能的减少浪费,于是虫虫给每个果子一个美味值,对于每个果子,请计算如果咬掉这个果子,它上面部分、下面部分和从树根到这个分叉点的路径中比这个果子更美味的果子各有多少个。,分析图例,算法,考虑一个点P,对树进行从左到右的深度优先遍历,那么在A,D部分的点会在P之前被访问,B,C在之后被访问。 同理,从右到左深度优先遍历,那么B,D先被访问,A,C后被访问。 对于求出的这两个序列,可以用nlogn求出序列中每个点之前有多少个点比它大。 也就是我们可以求出每个点的Fa+Fd,Fb+Fd(Fi表示在i部分中有多少点比固定点大) Fd可以用一遍深度优先遍历求出。,最长上升序列,设有整数序列b1,b2,b3,bm ,若存在下标i1i2i3in,且bi1bi2bi3 bin,则称 b1,b2,b3,bm中有长度为n的上升序列bi1 , bi2 ,bi3 ,bin 。 求序列b1,b2,b3,bm的最大上升长度n,以及所有长度为n的最大上升子序列个数t 输入:整数序列。 输出:n,t,分析,(1)设f(i)为前i个数中的最大不下降序列长度 , 则 f(i)=maxf(j)+1 (1=ji=m, bjbi) 边界为F(1)=1 (2)设t(i)为前i个数中最长不下降序列的个数,则 t(i)=t(j) (1=ji=m , bjbi, f(i)=f(j)-1) 初始为t(i)=1 当f(i)=n时,将t(i)累加 举例: 1 2 3 4 6 5 8 10 9 f: 1 2 3 4 5 5 6 7 7 t: 1 1 1 1 1 1 2 2 2 答案:f=7时,边界为t=4,进一步,(3)求本质不同的最长不下降序列个数有多少个? 如:1 2 3 4 6 5 8 10 9 有, 1 2 3 4 6 8 10 , 1 2 3 4 5 8 10, 1 2 3 4 6 8 9 ,1 2 3 4 5 8 9 都是本质不同的。 但对于 1 2 2 3 3 5 4 f 1 2 2 3 3 5 4 t 1 1 1 2 2 4 4 答案有8个,其中4个1 2 3 5 ,4个1 2 3 4,改进算法,上例显然对于相两个相同的数,重复算了多次因此,我们对算法进行改进: 对原序列按b从小到大(当bi=bj时按F从大到小)排序,增设Order(i)记录新序列中的i个数在原序列中的位置。可见, 求t(i)时,当f(j)=f(j+1),b(j)=b(j+1)且Order(j+1)Order(i)时,便不累加t(j)。这样就避免了重复。 上述算法的时间复杂度为O(n2),合唱队形(NOIP2005-3),给出N个人,第i个人的高度为Ai,现在要求找出一个对形,使得从某个人开始,前面的人都呈递增的顺序排列,后面的人呈递减顺序排列 找出最长的该队列.,解法,动态规划: 枚举中间最高的一个人,接着对它的左边求最长上升序列(注意序列中最高的同学不应高过基准),对右边求最长下降序列(同样的,序列中最高的同学不应高过基准)。时间复杂度为O(n2),算法实现起来也很简单。 接着对这个算法进行分析,我们不难发现,假如还是基于枚举一个同学的话,设Incsqi表示了1 - i的最长上升序列,Decsqi表示了i - n的最长下降序列,那么, Currenti = Incsqi + Decsqi - 1(两个数组中i被重复计算了) 那么,我们只需要先求好最长上升和下降序列,然后枚举中间最高的同学就可以了。,优化,求最长上升序列的经典状态转移方程为: opti = maxoptj+1, 其中ilisti 我们对状态转移方程稍微做一些修改: opti = maxopt(i+1), minj | recj=listi recj 记录当前不下降序列的最小值 很明显可以看出,在opti的寻找j的过程当中,查询序列是单调的,于是可以用二分法,就十分巧妙地在logn的时间内找到指定的j,而问题的总体复杂度为O(nlogn)。这样,这个问题的算法效率就得到了大幅度的提升,即便n是106,也可以轻松应对。,二叉堆,定义 n个元素的序列k1,k2,kn,当且仅当满足 ki=k2i 并且 ki = k2i+1 二叉堆肯定是一颗完全二叉树,堆的构造,第一步,构造一个初始堆 第二步,逐步调整该堆,使它符合堆的性质,堆排序算法,PROC shift (var r:listtype; k,m:integer); i:=k.j:=2*I; x:=rk.key;finish:=false t:=rk; while (jrj+1.key) then j:=j+1; If x=rj.key then finish:=true Else ri:=rj; i:=j; j:=2*I ri:=t endP PROC heapsort(var r:listtype); For i:=n/2 downto 1 shift(r,I,n); For i:=n downto 2 do r1与ri交换; shift(r,1,i-1) endP,合并果子,把合成堆后的每堆的果子仍然看成相对独立的,那么定义timesi等于第i堆果子被合并的次数,ai为第i堆数字权值。则 Totalcost= ,目标求得是 minTotalcost。 建立一棵二叉树,每堆果子分别为该树的叶节点,一种二叉树形态对应一种合并方案(2堆果子合并则有共同父结点),所以该方案的Totalcost =depthi*vi ,i是叶节点。解法是每次取出最小的两个节点,并从节点集合中删除,然后合并这两点后再加入节点集合;重复,直到只剩一个节点;,由于每次要取出最小的两个节点。一般做法是每更新一次集合,重新排序,时间是O(n2)。由于n=10000,不得不采用数据结构-堆进行优化。,最大子序和,问题描述 输入一个长度为的整数序列(A1,A2,An),从中找出一段连续的长度不超过M的子序列,使得这个序列的和最大。,最大子序和,例如: 序列 1, -3, 5, 1, -2, 3,当M=2或3时,S=5+1=6,当M=4时,S=5+1+(-2)+3=7,数据范围: 50%的数据N,M=1000 100%的数据N,M=20000,一个简化的问题,序列的最大连续和 输入一个长度为的整数序列(A1,A2,An),从中找出一段连续的子序列,使得这个序列的和最大。,和原问题相比没有M这个序列长度的限制!,分析:,设 F(i)表示以第i个数结尾的最大连续和,以第i个数结尾的最大连续和序列,可能存在两种选择: 情形一:只包含Ai 情形二:包含Ai和以Ai-1结尾的最大连续和序列,动态规划:,转移方程: F(i)=maxAi , F(i-1)+Ai 边界:F(1)=A1 要求的结果为maxF(i)|1=i=n,该算法的时间复杂度为O(n),一个简化的问题,例一 算法一枚举,设 F(i)为以Ai结尾长度不超过M的最大子序和,对于每个F(i),从1到m枚举k的值,完成Aj的累加和取最大值。,该算法的时间复杂度为O(n2),原问题初步分析,简化方程,用一个二叉堆来维护S(i-k),每次求F(i)之前的操作如下:,算法二堆,求F(i-1)时,求minS(i-m-1), ,S(i-2) 求F(i)时, 求minS(i-m),S(i-1),在堆中删除元素S(i-m-1),插入元素S(i-1).复杂度O(2log2n),从堆中取出当前最小值.复杂度O(1),所以计算的总复杂度为O(nlog2n),队列优化,在算法二中,考虑用队列来维护决策值S(i-k)。每次只需要在队首删掉S(i-m-1),在队尾添加S(i-1) 。但是取最小值操作还是需要O(n)时间复杂度的扫描。,考察在添加S(i-1)的时候,设现在队尾的元素是S(k),由于ki-1,所以S(k)必然比S(i-1)先出队。若此时S(i-1)=S(k),则S(k)这个决策永远不会在以后用到,可以将S(k)从队尾删除掉(此时队列的尾部形成了一个类似栈的结构),队列优化,同理,若队列中两个元素S(i)和S(j),若i=S(j),则我们可以删掉S(i)(因为S(i)永远不会被用到)。此时的队列中的元素构成了一个单调递增的序列,即:,S1S2S3Sk,算法三,我们来整理在求F(i)的时候,用队列维护S(i-k)所需要的操作:,若当前队首元素S(x),有x=i-m为止。,若当前队尾元素S(k)=S(i-1),则S(k)出队;直到S(k)S(i-1)为止。,在队尾插入S(i-1),取出队列中的最小值,即队首元素。,算法三,由于对于求每个F(i)的时候,进队和出队的元素不止一个。 但是我们可以通过分摊分析得知,每一个元素S(i)只进队一次、出队一次,所以队列维护的时间复杂度是O(n)。而每次求F(i)的时候取最小值操作的复杂度是O(1),所以这一步的总复杂度也是O(n)。 综上所述,该算法的总复杂度是O(n),小结,在本题的解决过程中,我们首先通过对于一个简化的问题解答,得到了该类问题一般性的解决思路,随后得到了一个O(n2)的算法 我们通过简化方程,进一步明确和细化了求解目标,运用合理的数据结构堆,得到了一个O(nlog2n)的算法。 通过进一步的挖掘求解目标的内涵,寻找内在规律,我们得到只用线性表维护的O(n)的算法。,过河(NOIP2005),在河上有一座独木桥,一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子,青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数,我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点:0,1,L(其中L是桥的长度)。坐标为0的点表示桥的起点,坐标为L的点表示桥的终点。青蛙从桥的起点开始,不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数(包括S,T)。当青蛙跳到或跳过坐标为L的点时,就算青蛙已经跳出了独木桥。 题目给出独木桥的长度L,青蛙跳跃的距离范围S,T,桥上石子的位置。你的任务是确定青蛙要想过河,最少需要踩到的石子数。,【输入文件】 输入文件river.in的第一行有一个正整数L(1 = L = 109),表示独木桥的长度。第二行有三个正整数S,T,M,分别表示青蛙一次跳跃的最小距离,最大距离,及桥上石子的个数,其中1 = S = T = 10,1 = M = 100。第三行有M个不同的正整数分别表示这M个石子在数轴上的位置(数据保证桥的起点和终点处没有石子)。所有相邻的整数之间用一个空格隔开。 【输出文件】 输出文件river.out只包括一个整数,表示青蛙过河最少需要踩到的石子数。 【样例输入】 10 2 3 5 2 3 5 6 7 【样例输出】 2 【数据规模】 对于30%的数据,L = 10000; 对于全部的数据,L = 109。,分析,由于不能往回跳,很容易想到用动态规划解决这个题目。 设f(i)表示跳到第i个点需要踩到的最少石子数,则很容易写出动态规划的状态转移方程:,时间复杂度是O(L*(T-S),但本题的L高达109,根本无法承受!,进一步分析,我们先来考虑这样一个问题:长度为k的一段没有石子的独木桥,判断是否存在一种跳法从一端正好跳到另一端。 若S=MaxK,都可以从一端正好跳到另一端。 题设中1=S=T=10,经过简单推导或者程序验证就可以发现,取MaxK=100就能满足所有区间。,于是我们可以分两种情况讨论: 1. S=T时: 这时候由于每一步只能按固定步长跳,所以若第i个位置上有石子并且i mod S=0那么这个石子就一定要被踩到。这是我们只需要统计石子的位置中哪些是S的倍数即可。复杂度O(M) 2. SMaxK+2*T,我们就将这段区域缩短成长度为MaxK+2*T。可以证明处理之后的最优值和原先的最优值相同。,如上图所示,白色点表示连续的一长段长度大于MaxK+2*T的空地,黑色点表示石子。设原先的最优解中,白色段的第一个被跳到的位置a,最后一个被跳到的位置是b,则在做压缩处理之后,a和b的距离仍然大于MaxK,由上面的结论可知,必存在一种跳法从a正好跳到b,而且不经过任何石子。,所以原来的最优解必然在处理之后的最

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论