搜索与动态规划

1、枚举、搜索与动态规划试 题 精 讲朱全民枚举 所谓枚举法所谓枚举法,指的是从可能的解集合中一一枚举各指的是从可能的解集合中一一枚举各元素元素,用题目给定的检验条件判定哪些是无用的用题目给定的检验条件判定哪些是无用的,哪些是有用的哪些是有用的.能使命题成立能使命题成立,即为其解。一般思即为其解。一般思路：路： 对命题建立正确的数学模型；对命题建立正确的数学模型； 根据命题确定的数学模型中各变量的变化范围根据命题确定的数学模型中各变量的变化范围（即可能解的范围）；（即可能解的范围）； 利用循环语句、条件判断语句逐步求解或证明；利用循环语句、条件判断语句逐步求解或证明； 枚举法的特点是算法简单，但有

2、时运算量大。对枚举法的特点是算法简单，但有时运算量大。对于可能确定解的值域又一时找不到其他更好的算于可能确定解的值域又一时找不到其他更好的算法时可以采用枚举法。法时可以采用枚举法。 枚举法求解的问题必须满足两个条件：枚举法求解的问题必须满足两个条件： 可预先确定每个状态的元素个数可预先确定每个状态的元素个数n； 状态元素状态元素a1，a2，an的可能值为一个连续的值域。的可能值为一个连续的值域。设设ai1状态元素状态元素ai的最小值；的最小值；aik状态元素状态元素ai的最大值的最大值(1in)即即a11a1a1k , a21a2a2k ,ai1aiaik , , an1anankfor a1

3、a11 to a1k do fo a2a21 to a2k do for anan1 to ank do if 状态状态(a1，ai，an)满足检验条件满足检验条件 then 输出问题的解；输出问题的解；枚举算法的优化枚举算法的优化枚举算法的时间复杂度可以用状态总数枚举算法的时间复杂度可以用状态总数*考察单个状态的耗时考察单个状态的耗时来表示，因此优化主要是来表示，因此优化主要是减少状态总数（即减少枚举变量和枚举变量的值域）减少状态总数（即减少枚举变量和枚举变量的值域）降低单个状态的考察代价降低单个状态的考察代价优化过程从几个方面考虑。具体讲优化过程从几个方面考虑。具体讲提取有效信息提取有效信

4、息减少重复计算减少重复计算将原问题化为更小的问题将原问题化为更小的问题根据问题的性质进行截枝根据问题的性质进行截枝引进其他算法引进其他算法侦探推理侦探推理 (NOIP2003-2)证词中出现的其他话，都不列入逻辑推理的内容。证词中出现的其他话，都不列入逻辑推理的内容。明明所知道的是，他的同学中有明明所知道的是，他的同学中有N N个人始终说假话，其余的个人始终说假话，其余的人始终说真话。人始终说真话。现在，明明需要你帮助他从他同学的话中推断出谁是真正现在，明明需要你帮助他从他同学的话中推断出谁是真正的凶手，请记住，的凶手，请记住，凶手只有一个！凶手只有一个！要求：要求：判断谁是罪犯？判断谁是罪犯

5、？分析 这道题的关键点是这道题的关键点是“如何能够快速正确实现出来如何能够快速正确实现出来” ” ，事实，事实上这道题对编码能力的要求要大于对算法本身的要求。由上这道题对编码能力的要求要大于对算法本身的要求。由于这道题的数据范围并不是很大，但需要进行于这道题的数据范围并不是很大，但需要进行“字符串处字符串处理理”这种比较麻烦的工作，因此在比赛时就可以采用效率这种比较麻烦的工作，因此在比赛时就可以采用效率低一些的枚举算法来换取编码上的简单。低一些的枚举算法来换取编码上的简单。 推荐的算法分为两步：推荐的算法分为两步：1 1预处理每个人的每一句话，并把它们分类处理；预处理每个人的每一句话，并把它们

6、分类处理；2 2枚举罪犯和当前星期几，找出所有可能发生的情况。枚举罪犯和当前星期几，找出所有可能发生的情况。 下面我们来逐步细化一下每一步的算法，对于第一步，我下面我们来逐步细化一下每一步的算法，对于第一步，我们希望的是把一些杂乱的不好处理的们希望的是把一些杂乱的不好处理的“字符串信息字符串信息”转化转化为相对比较好处理的信息。为此，我们可以通过把为相对比较好处理的信息。为此，我们可以通过把“信息信息”进行分类的方法使得对于每一类信息，更加方便的处理进行分类的方法使得对于每一类信息，更加方便的处理（即我们可以用一个或者几个变量来表示），由题目描述（即我们可以用一个或者几个变量来表示），由题目描

7、述可以发现语句可分为三类：可以发现语句可分为三类：分析1 1指明指明i i是否是罪犯的语句；是否是罪犯的语句；2 2指明今天是星期指明今天是星期d d的语句；的语句；3 3没有意义的语句没有意义的语句( (不符合格式要求不符合格式要求) )。 我们必须要说明的是任何不符合格式要求的语句都将被划我们必须要说明的是任何不符合格式要求的语句都将被划分到第三类中去，这样在处理每个语句的时候就必须要考分到第三类中去，这样在处理每个语句的时候就必须要考虑该语句是否符合格式要求，通过以上的处理，我们对于虑该语句是否符合格式要求，通过以上的处理，我们对于每一个语句用几个变量就可以表示了。每一个语句用几个变量就

8、可以表示了。 对于第二步的细化，我们在枚举完罪犯和当前星期几之后，对于第二步的细化，我们在枚举完罪犯和当前星期几之后，就可以比较方便的判断每一句话的真伪了，这样我们再根就可以比较方便的判断每一句话的真伪了，这样我们再根据每个人所说的话把人进行分类。据每个人所说的话把人进行分类。1 1没说任何一句有意义的话；没说任何一句有意义的话；2 2只说真话；只说真话；3 3只说假话；只说假话；4 4既说真话也说假话。既说真话也说假话。分析 需要注意的是，对于第一类人我们既可以把他当成说真需要注意的是，对于第一类人我们既可以把他当成说真话的，也可以把他当成说假话的，而如果第四类人存在话的，也可以把他当成说假

9、话的，而如果第四类人存在的话，那么从他本身就可以推出矛盾了。的话，那么从他本身就可以推出矛盾了。 最后，如果对于罪犯最后，如果对于罪犯i i存在一个存在一个d d使得当前情况是可能的，使得当前情况是可能的，我们就说我们就说i i就是可能的罪犯。就是可能的罪犯。 时间效率时间效率 O(MP|Day|) O(MP|Day|) （其中（其中Day=SundayDay=Sunday，Monday, Tuesday, Monday, Tuesday, Wednesday, Thursday, Friday, SaturdayWednesday, Thursday, Friday, Saturday）优化

10、 我们可以发现在对罪犯和当前星期几进行我们可以发现在对罪犯和当前星期几进行“双重枚举双重枚举”时，时，进行了很多重复的操作，于是我们想到，能不能不枚举是当进行了很多重复的操作，于是我们想到，能不能不枚举是当前星期几？这样我们把这类语句与判断罪犯的语句分离，可前星期几？这样我们把这类语句与判断罪犯的语句分离，可以先由判断罪犯的语句中确定一部分人肯定说真话，一部分以先由判断罪犯的语句中确定一部分人肯定说真话，一部分人肯定说假话，剩下的一部分人就要根据他所说的当前星期人肯定说假话，剩下的一部分人就要根据他所说的当前星期几的语句来判断了，首先我们假设所有人判断星期的语句不几的语句来判断了，首先我们假设

11、所有人判断星期的语句不自相矛盾，这样每个人将在判断这类问题里面至多有一个答自相矛盾，这样每个人将在判断这类问题里面至多有一个答案，我们便可以统计判断当前是星期案，我们便可以统计判断当前是星期d d的总人数，于是改进的总人数，于是改进后的算法对于每一个可能的罪犯，先用后的算法对于每一个可能的罪犯，先用O(p)O(p)的时间处理所有的时间处理所有的话，再用的话，再用O(|Day|)O(|Day|)的时间枚举星期几。这样，改进后算法的时间枚举星期几。这样，改进后算法的复杂度就是的复杂度就是O(m(p+|Day|)O(m(p+|Day|)。 那么我们可不可以再进一步，把算法优化到线性？这里面可那么我们

12、可不可以再进一步，把算法优化到线性？这里面可以比较明确地告诉大家，是可以做到的，具体的算法类似于以比较明确地告诉大家，是可以做到的，具体的算法类似于上面的按照语句的种类分离语句，只是分离得更细，处理得上面的按照语句的种类分离语句，只是分离得更细，处理得更复杂，在这里就不做赘述，留给大家思考。更复杂，在这里就不做赘述，留给大家思考。现有一个棱长为现有一个棱长为n的立方体，可以分成的立方体，可以分成n3个个1*1*1的单位立方体。每个单位立方体都有的单位立方体。每个单位立方体都有一个整数值。一个整数值。n3个单位立方体的数和不会超过个单位立方体的数和不会超过longint范围。现在要求在这个立方体

13、找范围。现在要求在这个立方体找到一个包含完整单位立方体的长方体，使得该长方体内所有单位立方体的数和最大。到一个包含完整单位立方体的长方体，使得该长方体内所有单位立方体的数和最大。输入：输入： n(1n20)；n个个n*n的数字矩阵，每个数字矩阵代表一层，每个数字代表一的数字矩阵，每个数字矩阵代表一层，每个数字代表一个单位立方体的整数值，个单位立方体的整数值，-999单位立方体的整数值单位立方体的整数值999999输出：输出：长方体的数和长方体的数和1 1、“直译直译”枚举过程枚举过程forfor x11 to n do 枚举所有可能的平面枚举所有可能的平面 forfor x21 to n do

14、 forfor y11 to n do forfor y21 to n do forfor z11 to n do 枚举所有可能的上平面和下底面枚举所有可能的上平面和下底面 forfor z21 to n do 考察状态（考察状态（x1，y1，z1，x2，y2，z2）；）；立方体问题考察状态（考察状态（x1，y1，z1，x2，y2，z2）的任务是计算长方体的体积，并调整最优解。设）的任务是计算长方体的体积，并调整最优解。设map为立方体对应的三维矩阵；为立方体对应的三维矩阵；sum为当前长方体的体积；为当前长方体的体积；best为最优解。考察过程为最优解。考察过程如下如下 sum00； for

15、for xxx1 1 to x2 do 计算长方体的体积计算长方体的体积 forfor yyy1 1 to y2 do forfor zzz1 1 to z2 do sumsum+mapxsum+mapx，y y，zz； 调整最优解调整最优解 if sumbest then bestsum if sumbest then bestsum；这个算法相当粗糙，枚举状态的费用为这个算法相当粗糙，枚举状态的费用为O O（n n9 9） 2 2、从减少重复计算入手、从减少重复计算入手记录先前考察的结果。在统计长方体记录先前考察的结果。在统计长方体2时，只要将长方体时，只要将长方体1的统计结果加上长方体的

16、统计结果加上长方体3就可以了，而就可以了，而不必按上述算法那样重新进行计算。不必按上述算法那样重新进行计算。 forfor x11 to n do 枚举所有可能的水平面枚举所有可能的水平面 forfor x21 to n do forfor y11 to n do forfor y21 to n do forfor z11 to n do 枚举上平面的枚举上平面的z轴坐标轴坐标 begin sum00； 长方体的体积初始化长方体的体积初始化 forfor z21 to n do 枚举下底面的枚举下底面的z轴坐标轴坐标 考察状态（考察状态（x1，y1，z1，x2，y2，z2）；）； end en

17、d；forfor考察过程改为考察过程改为 forfor xxx1 1 to x2 do 计算长方体的体积计算长方体的体积 forfor yyy1 1 to y2 do sumsum+mapxsum+mapx，y y，z z2 2 ； if sumbest then bestsumif sumbest then bestsum； 调整最优解调整最优解 由于利用了计算出的结果，整个算法的时间复杂度降为由于利用了计算出的结果，整个算法的时间复杂度降为O O（n n8 8）。）。3 3、提取恰当的信息、提取恰当的信息上述考察实际上求出z轴坐标为z2的平面中矩形（x1，y1，x2，y2）的数和。我们将这

18、个数和记为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，zRecRec数组可以在输入数据的同时计算数组可以在输入数据的同时计算fillchar(recfillchar(rec，size(rec)size(rec)，0)0)；recrec数组初始化

19、数组初始化 forfor z1 to n do 逐层输入信息逐层输入信息 forfor x1 to n do 逐行输入逐行输入z平面的信息平面的信息 begin forfor y1 to n do 逐列输入逐列输入z平面上平面上x行的信息行的信息beginbegin read(mapx read(mapx，y y，z)z)； 输入输入z z平面上（平面上（x,yx,y）中的数）中的数 if (x=1)and(y=1) if (x=1)and(y=1) 计算计算z z平面上以（平面上以（1 1，1 1）为左上角、（）为左上角、（x,yx,y）为右下角的矩形的数和）为右下角的矩形的数和 then

20、rec1then rec1，1 1，zmap1zmap1，1 1，zzelse if y=1 then recxelse if y=1 then recx，y y，zrecx-1zrecx-1，n n，z+mapxz+mapx，y y，zz else recx else recx，y y，zrecxzrecx，y-1y-1，z+mapxz+mapx，y y，zz； end end；forfor readln readln； end end；forfor这样，考察过程就可以改为这样，考察过程就可以改为 sumsum+recx sumsum+recx2 2，y y2 2，z z2 2+recx+r

21、ecx1 1，y y1 1，z z2 2-recx-recx2 2，y y1 1，z z2 2-recx-recx1 1，y y2 2，z z2 2 ； if sumbest then bestsum if sumbest then bestsum；时间复杂度降为时间复杂度降为O O（n n6 6）。）。如果长方体如果长方体a的数和是负数，则长方体的数和是负数，则长方体a的计算结的计算结果废弃，考察长方体果废弃，考察长方体b-a。因为长方体。因为长方体b的数和的数和=长方体长方体b-a的数和的数和+长方体长方体a的数和，由于长方体的数和，由于长方体a的数和为负，长方体的数和为负，长方体b-a的

22、数和一定大于等于长的数和一定大于等于长方体方体b的数和。由此可见，在累计长方体数和的的数和。由此可见，在累计长方体数和的时候，只要由上而下地枚举长方体下底面的时候，只要由上而下地枚举长方体下底面的z轴轴坐标即可。设坐标即可。设total(z)以以z轴坐标为轴坐标为z的平面为下底面的长方的平面为下底面的长方体的最大数和体的最大数和0, 1, 1, 1, 1,)1(, 0max(00)(21121122zzyxreczyxreczyxreczyxrecztotalzZTOTALforfor x11 to n do 枚举所有可能的子平面枚举所有可能的子平面 forfor x21 to n do fo

23、rfor y11 to n do forfor y21 to n do begin total00； 长方体以长方体以(x(x1 1,y,y1 1) )为左上角为左上角,(x,(x2 2,y,y2 2) )为右下角）的最大数和初始化为右下角）的最大数和初始化 for for z1 to n do 枚举枚举长方体长方体b b下底面的下底面的z z轴坐标轴坐标 begin totalmaxtotaltotalmaxtotal，0+0+ recx2，y2，z+ recx1-1，y1-1，z-recx2，y1-1，z-recx-1-1，y2，z； 计算以计算以z为下底面的长方体为下底面的长方体b的最大

24、数和的最大数和 if total best then besttotaltotal； 调整最优解调整最优解 end end；forfor end end；forfor这一改进使得考察的状态整数降为这一改进使得考察的状态整数降为O(nO(n5 5) ) 子串子串 给定一个由自然数串联而成的无限数列1234567891011121314（母串） 求任意一个长度不超过200的数列（子串）在其中最早出现的位置。分析： 首先，由于母串可无限扩充，显然我们不可能把它全部生成出来。 如果边生成母串，边判断所生成的数串是否包含给定的子串，即使是使用字符串处理中高效的KMP算法，耗费的工作量也是巨大的。1121

25、314 先枚举第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位出现（k=La）判断接下来由a生成的序列是否与子串吻合。如果

26、吻合，则最优解的判断：(1) LaAns_k4跟据Ans_a及Ans_k计算出位数 总时间复杂度约为O(n3)，与之前的不可估量相比有了本质性提高。 第4步可通过多种途径求得，这里不作介绍。 由于其中牵涉到许多高精度的计算及字符串处理，要求我们细致认真。小结 充分挖掘题目特性是解决本题的关键。 得以使枚举这类看似低效率的方法得到较好的运用。 同时细致全面的考虑问题也是必不可少的。宽度优先遍历算法框架 从某个未被访问的顶点从某个未被访问的顶点v出发出发,依次访问依次访问v的各个未曾访问过的各个未曾访问过的邻接点的邻接点.然后分别从这些邻接点出发广度优先搜索遍历然后分别从这些邻接点出发广度优先搜索

27、遍历,直直到所有已被访问的邻接点都被访问到到所有已被访问的邻接点都被访问到. 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) 在兰兰的模型中，神经网络就是一张有向图，图中的节点在兰兰的模型中，

28、神经网络就是一张有向图，图中的节点称为神经元，而且两个神经元之间至多有一条边相连，下称为神经元，而且两个神经元之间至多有一条边相连，下图是一个神经元的例子：图是一个神经元的例子： 图中，图中，X1X3X1X3是信息输入渠道，是信息输入渠道，Y1Y1Y2Y2是信息输出渠道，是信息输出渠道，C1C1表示神经元目前的状态，表示神经元目前的状态，UiUi是阈值，可视为神经元的一个是阈值，可视为神经元的一个内在参数。内在参数。 神经元按一定的顺序排列，构成整个神经网络。在兰兰神经元按一定的顺序排列，构成整个神经网络。在兰兰的模型之中，神经网络中的神经无分为几层；称为输入层、的模型之中，神经网络中的神经无

29、分为几层；称为输入层、输出层，和若干个中间层。每层神经元只向下一层的神经元输出层，和若干个中间层。每层神经元只向下一层的神经元输出信息，只从上一层神经元接受信息。输出信息，只从上一层神经元接受信息。 神经网络神经网络兰兰规定，兰兰规定，C Ci i服从公式：（其中服从公式：（其中n n是网络中所有神经元的数目）是网络中所有神经元的数目）E) i , j (ijjiiUCWC 公式中的公式中的WjiWji（可能为负值）表示连接（可能为负值）表示连接j j号神经元和号神经元和 i i号神经号神经元的边的权值。当元的边的权值。当 CiCi大于大于0 0时，该神经元处于兴奋状态，否时，该神经元处于兴奋

30、状态，否则就处于平静状态。当神经元处于兴奋状态时，下一秒它会则就处于平静状态。当神经元处于兴奋状态时，下一秒它会向其他神经元传送信号，信号的强度为向其他神经元传送信号，信号的强度为CiCi。 如此在输入层如此在输入层神经元被激发之后，整个网络系统就在信息传输的推动下进神经元被激发之后，整个网络系统就在信息传输的推动下进行运作。现在，给定一个神经网络，及当前输入层神经元的行运作。现在，给定一个神经网络，及当前输入层神经元的状态（状态（CiCi），要求你的程序运算出最后网络输出层的状态。），要求你的程序运算出最后网络输出层的状态。 【输入格式】【输入格式】 第一行是两个整数第一行是两个整数n n（

31、1n201n20）和）和p p。接下来。接下来n n行，每行两个行，每行两个整数，第整数，第i i1 1行是神经元行是神经元i i最初状态和其阈值（最初状态和其阈值（UiUi），非输入），非输入层的神经元开始时状态必然为层的神经元开始时状态必然为0 0。再下面。再下面P P行，每行由两个整行，每行由两个整数数i i，j j及一个整数及一个整数WijWij，表示连接神经元，表示连接神经元i i、j j的边权值为的边权值为WijWij。【输出格式】【输出格式】 输出包含若干行，每行有两个整数，分别对应一个神经元的输出包含若干行，每行有两个整数，分别对应一个神经元的编号，及其最后的状态，两个整数间以

32、空格分隔。编号，及其最后的状态，两个整数间以空格分隔。仅输出最仅输出最后状态非零的输出层神经元状态，并且按照编号由小到大顺后状态非零的输出层神经元状态，并且按照编号由小到大顺序输出！序输出！ 若输出层的神经元最后状态均为若输出层的神经元最后状态均为 0 0，则输出，则输出 NULLNULL。分析 理解问题的第一步就是认真理解问题的第一步就是认真“读题读题”。那么我们先来看。那么我们先来看一看这个题目涉及的问题。研究一下题目中所给的图的一看这个题目涉及的问题。研究一下题目中所给的图的一些性质，可以发现如下特点：一些性质，可以发现如下特点：1 1图中所有的节点都有一个确定的等级，我们记作图中所有的

33、节点都有一个确定的等级，我们记作Level(i)Level(i)2 2图中所有的边都是有向的，并且从图中所有的边都是有向的，并且从LevelLevel值为值为i-1i-1的节的节点指向点指向LevelLevel值为值为i i的节点的节点 我们不妨将其抽象为我们不妨将其抽象为“阶段图阶段图”。 更一般地，我们可以发现所有的阶段图都是有向无环的，更一般地，我们可以发现所有的阶段图都是有向无环的，这样我们可以通过拓扑排序来得到期望的处理节点的顺这样我们可以通过拓扑排序来得到期望的处理节点的顺序。序。可行算法 由于阶段图的性质使得该图的所有边所连接节点的等级由于阶段图的性质使得该图的所有边所连接节点的

34、等级都是相邻的，因此就可以设计出一个基于宽度优先搜索都是相邻的，因此就可以设计出一个基于宽度优先搜索（即（即BFSBFS）的算法：）的算法：1 1初始时将所有输入层的节点放入队列；初始时将所有输入层的节点放入队列；2 2取出队列中的一个元素，不重复地扩展并处理该节点所发出的取出队列中的一个元素，不重复地扩展并处理该节点所发出的边的目标节点；边的目标节点；3 3如果队列非空，则转向如果队列非空，则转向2 2；4 4输出输出层中所有满足条件的节点。输出输出层中所有满足条件的节点。 但是由于本题在问题描述中并没有明确的给出判断一个但是由于本题在问题描述中并没有明确的给出判断一个节点是否是输入节点，因

35、此需要在算法进行的过程当中节点是否是输入节点，因此需要在算法进行的过程当中额外地考虑一些边界情况的数据（这个过程即便是真实额外地考虑一些边界情况的数据（这个过程即便是真实数据没有这样出也是要有的），下面给出的更一般的算数据没有这样出也是要有的），下面给出的更一般的算法可能会更好的跳过这些边界情况。法可能会更好的跳过这些边界情况。1 1对原图中所有的节点进行一次拓扑排序；对原图中所有的节点进行一次拓扑排序；2 2按照拓扑顺序处理每一个节点；按照拓扑顺序处理每一个节点；3 3输出输出层中所有满足条件的节点。输出输出层中所有满足条件的节点。Amazing Robots: IOI2003已知条件： 迷

36、宫 i（i=1,2） （每个不会大于20*20） 守卫 Gi（0=Gi=10） （守卫循环移动进行执勤） （守卫巡逻的方格数（2.4）求： 两个机器人都离开迷宫所用的最少指令数目 和离开制指令序列（10000 步以内）。每一步可以发出的命令可以是N, E, S, W中的一种，有4种选择。对每一步具体发出哪个命令，直接搜索。假设最后结果是T。（也就是最少出宫时间）时间复杂度是O(4T)这种方法时间复杂度太高，绝对不可行!5*4和4*4的迷宫第一个机器人的位置是(2,2)第二个机器人的位置是(3,2)当前时间是0。状态(2,2),(3,2),0)状态表示：状态表示： （第一个机器人位置，第二个机器

37、认位置，时间）（第一个机器人位置，第二个机器认位置，时间）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=1

38、0000，这是状态数过多的罪魁祸首！题目说：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出发出发,深度优先遍历

39、图深度优先遍历图,直到直到和和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进制的虫食算式，相同的字母代表相进制的虫食算式，相同的字母代表相同的数字，不同的字母代表不同的数字。要求求同的数字，不同的字母代表不同的数字。要求求出满足这个算式的唯一一组解，也就是字母和数出满足这个算式的唯一一组解，也就是字母和数字的一一对应

40、关系字的一一对应关系.解决方案解决方案1:要求一一对应的关系，就可以枚举这些一要求一一对应的关系，就可以枚举这些一一对应的关系，找出符合的一项。这样，一对应的关系，找出符合的一项。这样，关系总数有关系总数有O(N!)个，最坏情况下必须枚举个，最坏情况下必须枚举所有的关系，并且加以判断，复杂度高达所有的关系，并且加以判断，复杂度高达O(N*N!)！ 解决方案解决方案2: 大体上，从算式最后一位开始模拟运算情况，当可递推时递推，大体上，从算式最后一位开始模拟运算情况，当可递推时递推，不可递推则枚举。不可递推则枚举。 对于一竖列，先处理两个加数，当遇到的字母的值不确定时，对于一竖列，先处理两个加数，

41、当遇到的字母的值不确定时，则枚举当前位（注意与前面的情况判重）；否则不作为处理和，则枚举当前位（注意与前面的情况判重）；否则不作为处理和，当遇到的字母的值不确定时当遇到的字母的值不确定时,可从加数部分确定的值来确定可从加数部分确定的值来确定（注意与前面的情况判重和进位）；否则看加数部分确定的值（注意与前面的情况判重和进位）；否则看加数部分确定的值是否能得到和部分（注意进位）。引出矛盾就回溯。是否能得到和部分（注意进位）。引出矛盾就回溯。 如题目的样例：如题目的样例： 5 ABCED BDACE EBBAA 它最后一位的情况是它最后一位的情况是(D+E) mod N=A, 对于最后一位只要枚举对

42、于最后一位只要枚举D,E的情况；的情况；A 则可以由则可以由D,E的值递推而来。对于倒的值递推而来。对于倒2位位, (E+C+最后一位进位最后一位进位) mod N=A ；E的值可以用前面的结果；的值可以用前面的结果；枚举枚举C；判断；判断A是否为是否为(D+C+最后一位进位最后一位进位) mod N虽然复杂度还是虽然复杂度还是O(N!)，但这种方法限制很多（相当于剪，但这种方法限制很多（相当于剪枝）。枝）。 解决方案解决方案3: 观察题目的条件已经限制得很苛刻：观察题目的条件已经限制得很苛刻：N个变量，每个个变量，每个至少出现一次；而且正好一共有至少出现一次；而且正好一共有N位的算式。这样就

43、位的算式。这样就构成了解方程的动机。这构成了解方程的动机。这N个变量的对应个变量的对应N个未知量，个未知量，有有N位的算式对应位的算式对应N个方程；个方程；N个未知量，个未知量，N个方程，个方程，正好可以得到唯一解。这里要注意，对解的要求很严正好可以得到唯一解。这里要注意，对解的要求很严格：必须是格：必须是0至至N-1的每个整数都正好出现一次。的每个整数都正好出现一次。但对每位式子的进位关系并不清楚，而进位关系但对每位式子的进位关系并不清楚，而进位关系正好影响了方程的常数项。枚举每位是否进位。用时正好影响了方程的常数项。枚举每位是否进位。用时O(2n), (因为首位不可能进位，无须枚举因为首位

44、不可能进位，无须枚举)。然后，用。然后，用高斯消元法来解方程。可以在枚举之前先解出方程，高斯消元法来解方程。可以在枚举之前先解出方程，枚举的时候再把参数带入。带入求解的复杂度是枚举的时候再把参数带入。带入求解的复杂度是O(n2) 。 解决方案解决方案4: 在解决方案在解决方案3的基础上，我们可以对进位的枚举剪枝。的基础上，我们可以对进位的枚举剪枝。观察这个竖列：观察这个竖列：A+B=C，若无进位则有，若无进位则有A=C且且BC且且B=C.若能推导出若能推导出A=A （A,B为任何不相等为任何不相等字母），则当前的枚举不可行。可用递归枚举，从字母），则当前的枚举不可行。可用递归枚举，从后向前枚举

45、，处理一个竖列时则加上后向前枚举，处理一个竖列时则加上2个不等式，看个不等式，看是否矛盾。数据结构用邻接矩阵。（规定是否矛盾。数据结构用邻接矩阵。（规定A=B，再，再有向图中有边有向图中有边）。）。 若加进不等式若加进不等式A=B ，要加入所有，要加入所有x(x=A) =y(B=y)，枚举，枚举x,y用用O(n2)得时间。再判断是否得时间。再判断是否有有x=y.森林中的果树 森林中长着一种奇怪的果树,在每个分叉处生长着果实，小虫Nileh和Nixed的食物就是这些果实！他们准备把果树分成两部分，每个虫虫得到各自的一部分，而分果树的方法就是选择一个分叉点，虫虫将他们咬断（自然分叉点上的果实也被扔

46、掉了），这样果树就变成了两个部分：分叉点上面的部分和分叉点下面的部分。 （注意,每个部分不一定是连在一起的）,比如对于右边这颗果树，如果他们咬掉蓝色的果子，那么就被分为红色和黄色的两个部分。 被咬掉的果子会被浪费，他们想尽可能的减少浪费，于是虫虫给每个果子一个美味值，对于每个果子，请计算如果咬掉这个果子，它上面部分、下面部分和从树根到这个分叉点的路径中比这个果子更美味的果子各有多少个。 分析图例算法 考虑一个点P，对树进行从左到右的深度优先遍历，那么在A,D部分的点会在P之前被访问，B,C在之后被访问。 同理，从右到左深度优先遍历，那么B,D先被访问，A,C后被访问。 对于求出的这两个序列，可

47、以用nlogn求出序列中每个点之前有多少个点比它大。 也就是我们可以求出每个点的Fa+Fd，Fb+Fd（Fi表示在i部分中有多少点比固定点大） Fd可以用一遍深度优先遍历求出。最长上升序列 设有整数序列设有整数序列b b1 1,b,b2 2,b,b3 3,b,bm m ，若存在下标，若存在下标i1i2i3ini1i2i3in，且，且b bi1i1bbi2i2bbi3i3 b binin，则，则称称 b b1 1,b,b2 2,b,b3 3,b,bm m中有长度为中有长度为n n的上升序列的上升序列b bi1 i1 , , b bi2 i2 ,b,bi3 i3 ,b,binin 。 求序列求序列

48、b b1 1,b,b2 2,b,b3 3,b,bm m的最大上升长度的最大上升长度n,n,以以及所有长度为及所有长度为n n的的最大上升子序列个数最大上升子序列个数t t 输入：整数序列。输入：整数序列。 输出：输出：n,tn,t分析（1 1）设）设f f(i)为前为前i个数中的最大不下降序列长度个数中的最大不下降序列长度 , 则则 f(i)=maxf(j)+1 (1=jif(i)=maxf(j)+1 (1=ji=m=m, bjbi), bjbi) 边界为边界为F(1)=1F(1)=1(2)设设t t(i)(i)为前为前i i个数中最长不下降序列的个数个数中最长不下降序列的个数, ,则则 t(

49、i)=t(j) (t(i)=t(j) (1=ji1=ji=m , bjbi, f(i)=f(j)-1) =m , bjbi, f(i)=f(j)-1) 初始为初始为t t(i)=1(i)=1 当当f(i)=nf(i)=n时，将时，将t(i)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时，时，边界为边界为tt=4=4进一步(3)求本质不同的最长不下降序列个数有多少个？求本质不同的最长不下降序列个数有多少个？ 如：如：1 2 3 4 6 5 8 10 9 有，有， 1 2

50、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 b从小到大（当从小到大（当bi=bjbi=bj时按时按F F从大到小）从大到小）排序，增设排序，增设O

51、rder(i)Order(i)记录新序列中的记录新序列中的i i个数在原个数在原序列中的位置。可见，序列中的位置。可见， 求求t(i)t(i)时，当时，当f f(j)=f(j+1),b(j)=b(j+1)(j)=f(j+1),b(j)=b(j+1)且且Order(j+1)Order(i)Order(j+1)Order(i)时，便不累加时，便不累加t(j)t(j)。这样。这样就避免了重复。就避免了重复。 上述算法的时间复杂度为上述算法的时间复杂度为O(n2) 合唱队形合唱队形(NOIP2005-3) 给出给出N个人，第个人，第i个人的高度为个人的高度为Ai,现在要求现在要求找出一个对形找出一个对

52、形,使得从某个人开始使得从某个人开始,前面的人前面的人都呈递增的顺序排列都呈递增的顺序排列,后面的人呈递减顺序后面的人呈递减顺序排列排列 找出最长的该队列找出最长的该队列.解法解法 动态规划：动态规划： 枚举中间最高的一个人，接着对它的左边求最长上升序枚举中间最高的一个人，接着对它的左边求最长上升序列（注意序列中最高的同学不应高过基准），对右边求列（注意序列中最高的同学不应高过基准），对右边求最长下降序列（同样的，序列中最高的同学不应高过基最长下降序列（同样的，序列中最高的同学不应高过基准）。时间复杂度为准）。时间复杂度为O(n2)，算法实现起来也很简单。，算法实现起来也很简单。 接着对这个算

53、法进行分析，我们不难发现，假如还是基接着对这个算法进行分析，我们不难发现，假如还是基于枚举一个同学的话，设于枚举一个同学的话，设Incsqi表示了表示了1 - i的最长上升的最长上升序列，序列，Decsqi表示了表示了i - n的最长下降序列，那么，的最长下降序列，那么， Currenti = Incsqi + Decsqi - 1（两个数组中（两个数组中i被重被重复计算了）复计算了） 那么，我们只需要先求好最长上升和下降序列，然后枚那么，我们只需要先求好最长上升和下降序列，然后枚举中间最高的同学就可以了。举中间最高的同学就可以了。优化优化 求最长上升序列的经典状态转移方程为：求最长上升序列的

54、经典状态转移方程为： opti = maxoptj+1, 其中其中ijlisti 我们对状态转移方程稍微做一些修改：我们对状态转移方程稍微做一些修改： opti = maxopt(i+1), minj | recj=listi recj 记录当前不下降序列的最小值记录当前不下降序列的最小值 很明显可以看出，在很明显可以看出，在opti的寻找的寻找j的过程当中，的过程当中，查询序列是单调的，于是可以用二分法，就十分查询序列是单调的，于是可以用二分法，就十分巧妙地在巧妙地在logn的时间内找到指定的的时间内找到指定的j，而问题的，而问题的总体复杂度为总体复杂度为O(nlogn)。这样，这个问题的算

55、法。这样，这个问题的算法效率就得到了大幅度的提升，即便效率就得到了大幅度的提升，即便n是是106，也可，也可以轻松应对。以轻松应对。二叉堆 定义定义 n个元素的序列个元素的序列k1,k2,kn，当且仅当满，当且仅当满足足 ki=k2i 并且并且 ki =k2i 并且并且 ki = k2i+1 二叉堆肯定是一颗完全二叉树二叉堆肯定是一颗完全二叉树堆的构造 第一步第一步,构构造一个初始造一个初始堆堆 第二步第二步,逐逐步调整该堆步调整该堆,使它符合堆使它符合堆的性质的性质堆排序算法PROC shift (var r:listtype; k,m:integer); i:=k.j:=2*I; x:=r

56、k.key;finish:=false t:=rk; while (j=m) and not finish do if (jrj+1.key) then j:=j+1; If x=rj.key then finish:=true Else ri:=rj; i:=j; j:=2*I ri:=tendPPROC 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合并果子合并果子 把合成堆后的每堆的果子仍然看成相对独立的，把合成堆后

57、的每堆的果子仍然看成相对独立的，那么定义那么定义timesi等于第等于第i堆果子被合并的次数，堆果子被合并的次数，ai为第为第i堆数字权值。则堆数字权值。则 Totalcost= ，目，目标求得是标求得是 minTotalcost。 建立一棵二叉树，每堆果子分别为该树的叶节点，建立一棵二叉树，每堆果子分别为该树的叶节点，一种二叉树形态对应一种合并方案（一种二叉树形态对应一种合并方案（2堆果子合堆果子合并则有共同父结点），所以该方案的并则有共同父结点），所以该方案的Totalcost =depthi*vi ，i是叶节点。解法是每次取出最小的是叶节点。解法是每次取出最小的两个节点，并从节点集合中删

58、除，然后合并这两两个节点，并从节点集合中删除，然后合并这两点后再加入节点集合；重复，直到只剩一个节点；点后再加入节点集合；重复，直到只剩一个节点； niiivtimes1 由于每次要取出最小的两个节点。一般做法是每更由于每次要取出最小的两个节点。一般做法是每更新一次集合，重新排序，时间是新一次集合，重新排序，时间是O(n2)。由于。由于n=10000，不得不采用数据结构，不得不采用数据结构-堆进行优化。堆进行优化。 )(2n)log(nn解决方案解决方案方法或要点方法或要点 时间复杂时间复杂度度可过数据可过数据解决方案解决方案1 一般做法一般做法30%-50%解决方案解决方案2堆堆100%最大

59、子序和最大子序和问题描述 输入一个长度为的整数序列（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个数结尾的最大连续和序列，可能存在两

60、种选择： 情形一：只包含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的最大子序和ikijjmkAiF1.1|max)( 对于每个F(i)，从1到m枚举k的值，完成Aj的累加和取最大值。该算法的时间复杂度为O(n2)原问题初步分析简化方程ikijjmkAiF1.1|max)(i1jjA) i (S令.1| )(min)(.1| )()(maxmkkiSiSmkkiSiS