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

《基础算法枚举贪心分治策略》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、基础算法策略长沙市第一中学曹利国第一部分枚举策略枚举策略的基本思想枚举法，又称穷举法，指在一个有穷的可能的解的集合中，一一枚举出集合中的每一个元素，用题目给定的检验条件来判断该元素是否符合条件，若满足条件，则该元素即为问题的一个解；否则，该元素就不是该问题的解。枚举策略的基本思想枚举方法也是一种搜索算法，即对问题的所有可能解的状态集合进行一次扫描或遍历。在具体的程序实现过程中，可以通过循环和条件判断语句来完成。枚举法常用于解决“是否存在”或“有多少种可能”等类型的问题。例如，求解不定方程的问题就可以采用列举法。虽然枚举法本质上属于搜索策略，但是它与回溯法

2、有所不同。因为适用枚举法求解的问题必须满足两个条件：      ⑴可预先确定每个状态的元素个数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输出问题的解；枚举策

3、略的基本思想枚举法的特点是算法比较简单，在用枚举法设计算法时，重点注意优化，减少运算工作量。将与问题有关的知识条理化、完备化、系统化，从中找出规律，减少枚举量。枚举方法的优化枚举算法的时间复杂度：状态总数*单个状态的耗时主要优化方法：⑴减少状态总数⑵降低单个状态的考察代价优化过程从以下几个方面考虑：⑴枚举对象的选取⑵枚举方法的确定⑶采用局部枚举或引进其他算法枚举算法的应用例题1：二进制数的分类若将一个正整数转化为二进制数后，0的个数多于1的个数的这类数称为A类数，否则称为B类数。例如：（13）10=（1101）2，13为B类数；（10）10=（1010）

4、210为B类数；（24）10=（11000）224为A类数；程序要求：求出1～1000之中（包括1与1000），全部A、B两类数的个数。【分析】此题是一道统计类题目。解决统计问题的一个常用方法是枚举法：逐一枚举所有情况，同时进行统计，枚举结束时，统计也完成，得到结果。具体对本题而言，采用枚举法的正确性与可行性是显然的，而本题的数据规模又仅为1～1000，所以采用逐一枚举方法进行统计的时间复杂度是完全可以接受的。枚举算法的应用例题2：01统计例题4：圆桌骑士（IOI试题）在一个8*8的棋盘上，有一个国王和若干个武士。其中，国王走一字步，骑士走马步。若国王与

5、骑士相会在同一点上，国王可以选择让骑士背他走。求一个点，使所有的骑士和国王相距在这个点上的所走的步数最少。枚举算法的应用【分析】此题可从3个方面考虑：分治、枚举、数学方法。由于无法将这个问题划分为各自独立的小问题来解决，分治显然是不行的。又因武士和国王位置的不固定性和其走法的差异，推导不出一个数学公式。因此考虑使用枚举，需要枚举的三个要点：1、最后的汇聚点。2、国王与背他的骑士的汇聚点。3、国王与背他的骑士。枚举算法的应用国王最多只会与一个骑士结合，因为骑士的最终目标也是最终汇聚点，一旦国王与某个骑士汇合后，即马上可与其结合，剩下的只需要将所有的骑士汇合

6、就可以了。更没有必要在中途中有将国王托付给其他的骑士。这样我们估算一下时间为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：=1to8dobe

7、ginForkk：=1tokdo{枚举与国王结合的武士}Ifdis[knight[kk].x,knight[kk].y,x,y]

8、车站最多用一条公路直接相连，从任何一个车站出发都可以经过一条或多条公路到达其他车