枚举搜索与动态规划试题精讲课件.ppt

《枚举搜索与动态规划试题精讲课件.ppt》由会员分享，可在线阅读，更多相关《枚举搜索与动态规划试题精讲课件.ppt（83页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

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

4、问题根据问题的性质进行截枝根据问题的性质进行截枝引进其他算法引进其他算法侦探推理侦探推理(NOIP20032)证词中出现的其他话，都不列入逻辑推理的内容。证词中出现的其他话，都不列入逻辑推理的内容。明明明明所所知知道道的的是是，他他的的同同学学中中有有N N个个人人始始终终说说假假话话，其其余余的的人始终说真话。人始终说真话。现现在在，明明明明需需要要你你帮帮助助他他从从他他同同学学的的话话中中推推断断出出谁谁是是真真正正的凶手，请记住，的凶手，请记住，凶手只有一个！凶手只有一个！要求：要求：判断谁是罪犯？判断谁是罪犯？分析这道题的关键点是这道题的关键点是“如何能够快速正确实现出来如何能够快速

5、正确实现出来”，事实，事实上这道题对编码能力的要求要大于对算法本身的要求。由上这道题对编码能力的要求要大于对算法本身的要求。由于这道题的数据范围并不是很大，但需要进行于这道题的数据范围并不是很大，但需要进行“字符串处字符串处理理”这种比较麻烦的工作，因此在比赛时就可以采用效率这种比较麻烦的工作，因此在比赛时就可以采用效率低一些的枚举算法来换取编码上的简单。低一些的枚举算法来换取编码上的简单。推荐的算法分为两步：推荐的算法分为两步：1 1预处理每个人的每一句话，并把它们分类处理；预处理每个人的每一句话，并把它们分类处理；2 2枚举罪犯和当前星期几，找出所有可能发生的情况。枚举罪犯和当前星期几，找

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

7、句；是否是罪犯的语句；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 forfor y11 to n do forfor y21 to n do forfor z11 to n do 枚举所有可能的上平面和下底

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

15、2 do sumsum+mapxsum+mapx，y y，zz；调整最优解调整最优解 if sumbest then bestsum if sumbest then bestsum；这个算法相当粗糙，枚举状态的费用为这个算法相当粗糙，枚举状态的费用为O O（n n9 9）2 2、从减少重复计算入手、从减少重复计算入手记记录录先先前前考考察察的的结结果果。在在统统计计长长方方体体2时时，只只要要将将长长方方体体1的的统统计计结结果果加加上上长长方方体体3就就可可以以了了，而而不必按上述算法那样重新进行计算。不必按上述算法那样重新进行计算。forfor x11 to n do 枚举所有可能的水平面

16、枚举所有可能的水平面 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 end；forfor考察过程改为考察过程改为 forfor xxx1 1 to x2 do 计算长方体的体积计算长方体的体积 forfor yyy1 1 to y2 do su

17、msum+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）的数和。我们将这个数和记为value(a)value(A)=value(ABCD)+value(B)-value(BC)-value(BD)这就启发我们用另一种方法表示立方体的信息：设recx，

18、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数组初始化数组初始化 forfor z1 to n do 逐层输入信息逐层输入信息 forfor x1 to n do 逐行输入逐行输入z平面的信息平面的信息 begin forfor y1

19、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 rec1then rec1，1 1，zmap1zmap1，1 1，zzelse if y=1 then recxelse if y=1 then recx，y y，zrecx-1zrecx-1

20、，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+recx1 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 best if

21、 sumbest then bestsumsum；时间复杂度降为时间复杂度降为O O（n n6 6）。）。如如果果长长方方体体a的的数数和和是是负负数数，则则长长方方体体a的的计计算算结结果果废废弃弃，考考察察长长方方体体b-a。因因为为长长方方体体b的的数数和和=长长方方体体b-a的的数数和和+长长方方体体a的的数数和和，由由于于长长方方体体a的的数数和和为为负负，长长方方体体b-a的的数数和和一一定定大大于于等等于于长长方方体体b的的数数和和。由由此此可可见见，在在累累计计长长方方体体数数和和的的时时候候，只只要要由由上上而而下下地地枚枚举举长长方方体体下下底底面面的的z轴轴坐标即可。设坐

22、标即可。设total(z)以以z轴轴坐坐标标为为z的的平平面面为为下下底底面面的的长长方方体的最大数和体的最大数和forfor x11 to n do 枚举所有可能的子平面枚举所有可能的子平面 forfor x21 to n do forfor 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 t

23、otalmaxtotaltotalmaxtotal，0+0+recx2，y2，z+recx1-1，y1-1，z-recx2，y1-1，z-recx-1-1，y2，z；计算以计算以z为下底面的长方体为下底面的长方体b的最大数和的最大数和 if total best then besttotaltotal；调整最优解调整最优解 end end；forfor end end；forfor这一改进使得考察的状态整数降为这一改进使得考察的状态整数降为O(nO(n5 5)子串子串给定一个由自然数串联而成的无限数列1234567891011121314（母串）求任意一个长度不超过200的数列（子串）在其中最

24、早出现的位置。分析：首先，由于母串可无限扩充，显然我们不可能把它全部生成出来。如果边生成母串，边判断所生成的数串是否包含给定的子串，即使是使用字符串处理中高效的KMP算法，耗费的工作量也是巨大的。1121314先枚举第1位1自然数1之后为2,3,母串中形如123与子串从第2位开始不符枚举前2位11自然数11之后为12,13母串中形如111213与子串从第3位开始不符考虑第2位开始12自然数12之前为11,末位与子串第1位相同，之后为13,14,母串中形如1314与子串匹配！如何优化呢？较好的方法是另辟蹊径：刚才我们枚举的是母串的每一位，不妨换一个角度，从子串着手。先来观察一些片断：123456

25、78910111213141516很自然得到算法：枚举子串所包含第一个完整的数a的位数La。假设a在母串的第k位出现（k=La）判断接下来由a生成的序列是否与子串吻合。如果吻合，则最优解的判断：(1)LaAns_k4跟据Ans_a及Ans_k计算出位数总时间复杂度约为O(n3)，与之前的不可估量相比有了本质性提高。第4步可通过多种途径求得，这里不作介绍。由于其中牵涉到许多高精度的计算及字符串处理，要求我们细致认真。小结充分挖掘题目特性是解决本题的关键。得以使枚举这类看似低效率的方法得到较好的运用。同时细致全面的考虑问题也是必不可少的。宽度优先遍历算法框架从某个未被访问的顶点从某个未被访问的顶点

26、v出发出发,依次访问依次访问v的各个未曾访问过的的各个未曾访问过的邻接点邻接点.然后分别从这些邻接点出发广度优先搜索遍历然后分别从这些邻接点出发广度优先搜索遍历,直到直到所有已被访问的邻接点都被访问到所有已被访问的邻接点都被访问到.PROCbfs(v);Visite(v);vistedv:=true;Iniqueue(q);enqueue(q,v);Whilenotempty(q)dov:=dlqueue(q);w:=FIRSTADJ(v);Whilew0doifnotvisitedwthenvisite(w);visitedw:=true;enqueue(q,w)w:=NEXTADJ(v,w

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

28、顺序排列，构成整个神经网络。在兰兰的模型之中，神经网络中的神经无分为几层；称为输入层、输出模型之中，神经网络中的神经无分为几层；称为输入层、输出层，和若干个中间层。每层神经元只向下一层的神经元输出信层，和若干个中间层。每层神经元只向下一层的神经元输出信息，只从上一层神经元接受信息。息，只从上一层神经元接受信息。神经网络神经网络兰兰规定，兰兰规定，C Ci i服从公式：（其中服从公式：（其中n n是网络中所有神经元的数目）是网络中所有神经元的数目）公公式式中中的的WjiWji（可可能能为为负负值值）表表示示连连接接j j号号神神经经元元和和 i i号号神神经经元元的的边边的的权权值值。当当 Ci

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

30、】第第一一行行是是两两个个整整数数n n（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。【输出格式】【输出格式】输输出出包包含含若若干干行行，每每行行有有两两个个整整数数，分分别别对对应应一一个个神神经经元元的的编编号号，及及其

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

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

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

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

35、迷宫 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)状态表示：状态表示：（第一个机器人位置，第二个机器认位置，时间）（

36、第一个机器人位置，第二个机器认位置，时间）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的位置状态：(positionofRobot1,positionofRobot2,Time)Time=10000，这是状态数过多的罪魁

37、祸首！题目说：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有路径的顶点都访

38、问到有路径的顶点都访问到.PROCdfs(v);visite(v);visitedv=true;w:=FIRSTADJ(v);whilew0doifnotvisitedwthendfs(w)w:=NEXTADJ(v,w);ENDP讨论讨论:虫食算问题虫食算问题给出一个给出一个N进制的虫食算式，相同的字母代表相进制的虫食算式，相同的字母代表相同的数字，不同的字母代表不同的数字。要求求同的数字，不同的字母代表不同的数字。要求求出满足这个算式的唯一一组解，也就是字母和数出满足这个算式的唯一一组解，也就是字母和数字的一一对应关系字的一一对应关系.解决方案解决方案1:要求一一对应的关系，就可以枚举这些一

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

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

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

42、式对应位的算式对应N个方程；个方程；N个未知量，个未知量，N个方程，个方程，正好可以得到唯一解。这里要注意，对解的要求很严正好可以得到唯一解。这里要注意，对解的要求很严格：必须是格：必须是0至至N-1的每个整数都正好出现一次。的每个整数都正好出现一次。但对每位式子的进位关系并不清楚，而进位关系但对每位式子的进位关系并不清楚，而进位关系正好影响了方程的常数项。枚举每位是否进位。用时正好影响了方程的常数项。枚举每位是否进位。用时O(2n),(因为首位不可能进位，无须枚举因为首位不可能进位，无须枚举)。然后，用高。然后，用高斯消元法来解方程。可以在枚举之前先解出方程，枚斯消元法来解方程。可以在枚举之

43、前先解出方程，枚举的时候再把参数带入。带入求解的复杂度是举的时候再把参数带入。带入求解的复杂度是O(n2)。解决方案解决方案4:在解决方案在解决方案3的基础上，我们可以对进位的枚举剪枝。的基础上，我们可以对进位的枚举剪枝。观察这个竖列：观察这个竖列：A+B=C，若无进位则有，若无进位则有A=C且且BC且且B=C.若能推导出若能推导出A=A（A,B为任何不相等为任何不相等字母），则当前的枚举不可行。可用递归枚举，从字母），则当前的枚举不可行。可用递归枚举，从后向前枚举，处理一个竖列时则加上后向前枚举，处理一个竖列时则加上2个不等式，看个不等式，看是否矛盾。数据结构用邻接矩阵。（规定是否矛盾。数据

44、结构用邻接矩阵。（规定A=B，再，再有向图中有边有向图中有边）。）。若加进不等式若加进不等式A=B，要加入所有，要加入所有x(x=A)=y(B=y)，枚举，枚举x,y用用O(n2)得时间。再判断是否得时间。再判断是否有有x=y.森林中的果树森林中长着一种奇怪的果树,在每个分叉处生长着果实，小虫Nileh和Nixed的食物就是这些果实！他们准备把果树分成两部分，每个虫虫得到各自的一部分，而分果树的方法就是选择一个分叉点，虫虫将他们咬断（自然分叉点上的果实也被扔掉了），这样果树就变成了两个部分：分叉点上面的部分和分叉点下面的部分。（注意,每个部分不一定是连在一起的）,比如对于右边这颗果树，如果他们

45、咬掉蓝色的果子，那么就被分为红色和黄色的两个部分。被咬掉的果子会被浪费，他们想尽可能的减少浪费，于是虫虫给每个果子一个美味值，对于每个果子，请计算如果咬掉这个果子，它上面部分、下面部分和从树根到这个分叉点的路径中比这个果子更美味的果子各有多少个。分析图例算法考虑一个点P，对树进行从左到右的深度优先遍历，那么在A,D部分的点会在P之前被访问，B,C在之后被访问。同理，从右到左深度优先遍历，那么B,D先被访问，A,C后被访问。对于求出的这两个序列，可以用nlogn求出序列中每个点之前有多少个点比它大。也就是我们可以求出每个点的Fa+Fd，Fb+Fd（Fi表示在i部分中有多少点比固定点大）Fd可以用

46、一遍深度优先遍历求出。最长上升序列 设设有有整整数数序序列列b b1 1,b,b2 2,b,b3 3,b,bm m ，若若存存在在下下标标i1i2i3ini1i2i3in，且且b bi1i1bbi2i2bbi3i3 bbinin，则则称称 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 。求求序序列列b b1 1,b,b2 2,b,b3 3,b,bm m的的最最大大上上升升长长度度n,n,以以及所有长度为及所有长度为n n的的最大上升子序列个数最大上升子序列个数t t输入：

47、整数序列。输入：整数序列。输出：输出：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(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

48、时，将时，将t(i)t(i)累加累加举例：举例：1234658109f:123455677t:111111222答案：答案：f=7时，时，边界为边界为tt=4=4进一步(3)求本质不同的最长不下降序列个数有多少个？求本质不同的最长不下降序列个数有多少个？如：如：1234658109有，有，12346810,12345810,1234689,1234589都是本质不同的。都是本质不同的。但对于但对于1223354f1223354t1112244答案有答案有8个，其中个，其中4个个1235，4个个1234改进算法上上例例显显然然对对于于相相两两个个相相同同的的数数，重重复复算算了了多多次次因因此，

49、我们对算法进行改进：此，我们对算法进行改进：对对原原序序列列按按b b从从小小到到大大（当当bi=bjbi=bj时时按按F F从从大大到到小小）排排序序，增增设设Order(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)。这这样样就避免了重复。就避免了重复。上述算法的时间复杂度为上述算法的时间

50、复杂度为O(n2)合唱队形合唱队形(NOIP2005-3)给出给出N个人，第个人，第i个人的高度为个人的高度为Ai,现在要求现在要求找出一个对形找出一个对形,使得从某个人开始使得从某个人开始,前面的人前面的人都呈递增的顺序排列都呈递增的顺序排列,后面的人呈递减顺序后面的人呈递减顺序排列排列找出最长的该队列找出最长的该队列.解法解法动态规划：动态规划：枚举中间最高的一个人，接着对它的左边求最长上升序列枚举中间最高的一个人，接着对它的左边求最长上升序列（注意序列中最高的同学不应高过基准），对右边求最长（注意序列中最高的同学不应高过基准），对右边求最长下降序列（同样的，序列中最高的同学不应高过基准）