基础算法[枚举、贪心、分治策略].ppt

基础算法策略;第一部分;枚举策略的基本思想 ;枚举策略的基本思想 ; 虽然枚举法本质上属于有哪些信誉好的足球投注网站策略，但是它与回溯法有所不同。因为适用枚举法求解的问题必须满足两个条件：?????? ⑴可预先确定每个状态的元素个数n； ⑵状态元素a1，a2，…，an的可能值为一个连续的值域。 设 ai1—状态元素ai的最小值；aik—状态元素ai的最大值(1≤i≤n)，即a11≤a1≤a1k，a21≤a2≤a2k， ai1≤ai≤aik，……，an1≤an≤ank for a1←a11 to a1k do fo a2←a21 to a2k do …………………… for ai←ai1 to aik do …………………… for an←an1 to ank do if 状态(a1，…，ai，…，an)满足检验条件 then 输出问题的解； ;枚举策略的基本思想 ;枚举方法的优化;枚举算法的应用;【分析】此题是一道统计类题目。解决统计问题的一个常用方法是枚举法：逐一枚举所有情况，同时进行统计，枚举结束时，统计也完成，得到结果。 具体对本题而言，采用枚举法的正确性与可行性是显然的，而本题的数据规模又仅为1～1000，所以采用逐一枚举方法进行统计的时间复杂度是完全可以接受的。;例题2：01统计;例题3：围巾裁剪（NOI试题） 将一个边长为n(n=100)的大的正三角形均匀的分成n*n的小三角形，某些小三角形已经损坏。求出2个面积最大的（即包含小三角形个数最多的）2个子正三角形，要求这两个子正三角形中没有损坏的小三角形。 ;【分析】 三角形的分割必定将沿着其分割线分割。由于n〈=100，将每个分割线枚举一次，最多只有100*3条，所以可以考虑用枚举求解。 枚举出分割线以后，我们当前最重要的任务就是如何求出上下2个三角形的最大子三角形。我们又可以使用枚举，以每一个点最为一次顶点，向下扩展，求出其可以扩展的最大面积。 为了减少枚举次数，我们可以考虑将其值先计算并保存下来。;定义变量： lup[I，j]表示以第I行j列的正放着的小三角形为上顶点的最大可扩展的面积。 ldown[I，j]表示以第I行j列的倒放着的小三角形为下顶点的最大可扩展的面积。 Up[I，j] 表示第I行j列的正放着的小三角形是否损坏。 down[I，j]表示以第I行j列的倒放着的小三角形是否损坏。; 容易得出lup，ldown[I，j]的递推式： min{lup[I+1,j],lup[I+1,j+1]}+1 [down[I+1,j]=true] lup[I,j]:= 1 [down[I+1,j]=false] 0 [up[I,j]=false] 边界：lup[n，I]：=1 min{ldown[I-1,j],ldown[I-1,j-1]}+1 [up[I-1,j]=true] ldown[I,j]:= 1 [up[I-1,j]=false] 0 [down[I,j]=false] 求出了lup，ldown后，算法的设计就不难了。;另外，还需要注意的一点是关于三角形60度的旋转。 对于正放着的三角形： xx：=n-y+1 yy：=x-（n-xx） 对于倒放着的三角形： xx：=n-y+1 yy：=x-1-（n-xx）;例题4：圆桌骑士（IOI试题） 在一个8*8的棋盘上，有一个国王和若干个武士。其中，国王走一字步，骑士走马步。若国王与骑士相会在同一点上，国王可以选择让骑士背他走。求一个点，使所有的骑士和国王相距在这个点上的所走的步数最少。;【分析】此题可从3个方面考虑： 分治、枚举、数学方法。 由于无法将这个问题划分为各自独立的小问题来解决，分治显然是不行的。又因武士和国王位置的不固定性和其走法的差异，推导不出一个数学公式。因此考虑使用枚举，需要枚举的三个要点： 1、最后的汇聚点。 2、国王与背他的骑士的