基础算法(枚举、贪心、分治策略)

基础算法策略长沙市第一中学曹利国第一部分枚举策略枚举策略的基本思想枚举法，又称穷举法，指在一个有穷的可能的解的集合中，一一枚举出集合中的每一个元素，用题目给定的检验条件来判断该元素是否符合条件，若满足条件，则该元素即为问题的一个解；否则，该元素就不是该问题的解。枚举策略的基本思想枚举方法也是一种搜索算法，即对问题的所有可能解的状态集合进行一次扫描或遍历。在具体的程序实现过程中，可以通过循环和条件判断语句来完成。枚举法常用于解决“是否存在”或“有多少种可能”等类型的问题。例如，求解不定方程的问题就可以采用列举法。虽然枚举法本质上属于搜索策略，但是它与回溯法有所不同。因为适用枚举法求解的问题必须满足两个条件：⑴可预先确定每个状态的元素个数n；⑵状态元素a1，a2，…，an的可能值为一个连续的值域。设ai1—状态元素ai的最小值；aik—状态元素ai的最大值(1≤i≤n)，即a11≤a1≤a1k，a21≤a2≤a2k，ai1≤ai≤aik，……，an1≤an≤ankfora1←a11toa1kdofoa2←a21toa2kdo……………………forai←ai1toaikdo……………………foran←an1toankdoif状态(a1，…，ai，…，an)满足检验条件then输出问题的解；枚举策略的基本思想枚举法的特点是算法比较简单，在用枚举法设计算法时，重点注意优化，减少运算工作量。将与问题有关的知识条理化、完备化、系统化，从中找出规律，减少枚举量。枚举方法的优化枚举算法的时间复杂度：状态总数*单个状态的耗时主要优化方法：⑴减少状态总数⑵降低单个状态的考察代价优化过程从以下几个方面考虑：⑴枚举对象的选取⑵枚举方法的确定⑶采用局部枚举或引进其他算法枚举算法的应用例题1：二进制数的分类若将一个正整数转化为二进制数后，0的个数多于1的个数的这类数称为A类数，否则称为B类数。例如：（13）10=（1101）2，13为B类数；（10）10=（1010）210为B类数；（24）10=（11000）224为A类数；程序要求：求出1～1000之中（包括1与1000），全部A、B两类数的个数。【分析】此题是一道统计类题目。解决统计问题的一个常用方法是枚举法：逐一枚举所有情况，同时进行统计，枚举结束时，统计也完成，得到结果。具体对本题而言，采用枚举法的正确性与可行性是显然的，而本题的数据规模又仅为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]：=1min{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+1yy：=x-（n-xx）对于倒放着的三角形：xx：=n-y+1yy：=x-1-（n-xx）枚举算法的应用例题4：圆桌骑士（IOI试题）在一个8*8的棋盘上，有一个国王和若干个武士。其中，国王走一字步，骑士走马步。若国王与骑士相会在同一点上，国王可以选择让骑士背他走。求一个点，使所有的骑士和国王相距在这个点上的所走的步数最少。枚举算法的应用【分析】此题可从3个方面考虑：分治、枚举、数学方法。由于无法将这个问题划分为各自独立的小问题来解决，分治显然是不行的。又因武士和国王位置的不固定性和其走法的差异，推导不出一个数学公式。因此考虑使用枚举，需要枚举的三个要点：1、最后的汇聚点。2、国王与背他的骑士的汇聚点。3、国王与背他的骑士。枚举算法的应用国王最多只会与一个骑士结合，因为骑士的最终目标也是最终汇聚点，一旦国王与某个骑士汇合后，即马上可与其结合，剩下的只需要将所有的骑士汇合就可以了。更没有必要在中途中有将国王托付给其他的骑士。这样我们估算一下时间为O（8*8*8*8*63）=O（36*10^4），完全可以承受。另外，我们需要预先将2点之间走马字步的距离计算出来。可以使用Floyd或是Bfs。枚举算法的应用算法流程：dis[x1，y1，x2，y2]--（x1，y1）（x2，y2）之间的距离。ForI：=1to8do{枚举汇合点}Forj：=1to8dobeginAll：=所有骑士到这一点的和；Best:=min(best,all+国王到汇聚点的步数)Forx：=1to8do{枚举武士国王的相会点}Fory：=1to8dobeginForkk：=1tokdo{枚举与国王结合的武士}Ifdis[knight[kk].x,knight[kk].y,x,y]minthenbeginMin:=dis[knight[kk].x,knight[kk].y,x,y];Mink:=k;End;End；Now:=all-mink武士走到汇合点的距离+mink武士走到汇聚点的距离+国王走到汇聚点的距离+从汇聚点到汇合点的距离；Best：=min（best，now）End；局部枚举例题5：求第一、第二、第三最短路问题局部枚举例题6：新年好重庆城里有n个车站，m条双向公路连接其中的某些车站。每两个车站最多用一条公路直接相连，从任何一个车站出发都可以经过一条或多条公路到达其他车站，但不同的路径需要花费的时间可能不同。在一条路上花费的时间等于路径上所有公路需要的时间之和。佳佳的家在车站1，他有五个亲戚，分别住在车站a,b,c,d,e。过年了，他需要从自己的家出发，拜访每个亲戚（顺序任意），给他们送去节日的祝福。怎样走，才需要最少的时间？分析这一题中的边数远小于n2，所以复杂度也只有nlogn+m算法框架是：（1）用5次最短路，计算出6个点两两之间的距离（2）枚举5个结点的全排列，找到一个使得总路程长度最短的方案。练习与讨论：阿凡提的烦恼从前国王总是为难阿凡提，但是每一次阿凡提都用他聪明的头脑一一化解了。但是这一次国王又来为难他了。国王这一次在一个用格子分好了的矩阵里面放了一些数字，然后国王想要阿凡提统计出所有字矩阵的和能被10整除的个数。刚开始，阿凡提还数得津津有味，可是发现随着矩阵的变大，这样的子矩阵的个数也大幅度的增多。而这个时候他也不甘心就这样被国王难住，可是要人工数，就显得太不现实了，于是阿凡提乘国王没注意的时候，悄悄摸摸请教了学习编程序的你。【输入】第一行为2个正整数n,m表示矩阵的长和宽(0n,m1000)。接下来有一个n行，m列的矩阵，矩阵的每个元素是一个正整数F[I,j](0F[I,j]maxlongint)。【输入】一共一行，为一个整数total(0=total=maxextended)，表示符合条件的子矩阵的个数。【样例】输入样例：13102030输出样例：6最大子矩阵的求解方法第二部分贪心方法贪心方法的基本思想贪心是一种解题策略，也是一种解题思想使用贪心方法需要注意局部最优与全局最优的关系，选择当前状态的局部最优并不一定能推导出问题的全局最优利用贪心策略解题，需要解决两个问题：该题是否适合于用贪心策略求解如何选择贪心标准，以得到问题的最优解适用于贪心策略求解的问题的特点适用于贪心策略求解的问题必须具有最优子结构的性质，但并不是所有具有最优子结构的问题都可以用贪心策略求解。因为贪心往往是盲目的，需要使用更理性的方法——动态规划（例如“0-1背包问题”与“部分背包问题”）贪心方法的应用例题1：节点网络。现有一个N！个节点的网络，每个节点的编号都是编号（A1A2A3…AN）序列的一个置换。对于任意两个节点S和T，如果T的编号是由S编号的首位与除首位外的编号中任一位交换所得，则S和T之间有一条边，求从给定节点S走到节点（A1A2A3…AN）所需经过的最少边数。其中，n≤100。贪心方法的应用例如n=3的情况：(A1A2A3)(A1A3A2)(A2A3A1)(A2A1A3)(A3A1A2)(A3A2A1)贪心方法的应用【分析】从题意表面上看，本题是一个求最短路径的问题，但题设中的N≤100，也就是说图中最多有100！个节点，采用二维关系的图结构根本无法存贮这众多的状态。通过问题的本质分析，可以将问题转化为一个序列的最优转化问题。贪心方法的应用采用贪心策略：每次让一个节点归位或为下一步工作做准备。其具体步骤为：若序列中第一个点为Ax(x≠1)，则将第一个点和第x个点交换。这便完成了让一个点归位的工作；若第一个是A1，则任找一个编号与位置不相符的点，并与之交换。这样下一步便可让交换到1号位置的点归位。贪心方法的应用(A3A4A1A2)(A1A4A3A2)第一个点A1已归位，但第二个点为A4≠A2，将第2个点A4与A1交换第一个点为A3≠A1，将第3个点A1与A3交换(A4A1A3A2)第一个点为A4≠A1，将第4个点A2与A4交换(A2A1A3A4)第一个点为A2≠A1，将第2个点A1与A2交换(A1A2A3A4)已经符合要求了一共经过4步完成。下面看一个n=4，初始序列为(A3A4A1A2)的推演过程：贪心方法的应用例题2：d-规则问题。对任意给定的m(m∈N+)和n(n∈N+)，满足mn，构造一初始集合：P={x|m≤x≤n,x∈N+}(m,n≤100)现定义一种d规则如下：若存在a∈P，且存在K∈N+,K1，使得Ka∈P，则修改P为：P=P-{y|y=sa,s∈N+}，并称该d规则具有分值a。现要求编制一个程序，对输入的m,n值，构造相应的初始集合P，对P每应用一次d规则就累加其相应的分值，求能得到最大累加分值的d规则序列，输出每次使用d规则时的分值和集合p的变化过程。贪心方法的应用【分析】初看这一问题，很容易想到用贪心策略来求解，即选择集合中最大的可以删除的数开始删起，直到不能再删除为止，而且通过一些简单的例子来验证，这一贪心标准似乎也是正确的，例如，当m=3，n=10时，集合P＝{3,…,10}，运用上述“贪心标准”可以得到这一问题的正确的最优解d=5＋4＋3＝12，即其d-规则过程如下：1.a=5P={3,4,6,7,8,9}d=52.a=4P={3,6,7,9}d=5+4=93.a=3p={7}d=5+4+3=12贪心方法的应用但是，如果再仔细地分析一个例子，当m=3，n＝18时，如果还是使用上述“贪心标准”，则得到问题的d-规则总分为d=35，其d-规则序列为（9,8,7,6,5），而实际上可以得到最大d-规则总分为d＝38，其对应的d-规则序列为（9,8,7,6,3,5