ACM基础算法入门教程.ppt

《ACM基础算法入门教程.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ACM基础算法入门.基础动态规划.基础的“穷竭搜索”.贪心的三种区间问题.数论那些事.二分的另类法引言算法简单但思想及其重要介绍的算法都堪称为经典中的经典基础动态规划多阶段决策过程最优化的数学方法三要素：-阶段-决策-状态动态规划的适用范围最优子结构（最优化原理）当前状态依赖于前面的状态得到，是前面状态的完美总结无后效性（不成环）经典模型数塔模型背包问题区间最大和模型最长非降子序列模型最长公共子序列数字归并（区间dp）旅行商问题（状态压缩）求解从顶到下经过节点的最大值是多少解题思路列状态v[I][j]表示走到第i层的第j个节点的最大值分阶段每一个层就是一个阶段状态转移方程（决策）V[i

2、-1][j]+=V[I][j]>v[I][j+1]?V[I][j]:v[I][j+1];单调递增非降子序列给定一整型数列{a1,a2...,an}（0

3、间覆盖选择不相交区间数轴上有n个开区间（ai,bi），选择尽量多个区间，使得这些区间两两没有公共点。【分析】首先明确一个问题：假设有两个区间x,y,区间x完全包含y。那么，选x是不划算的，因为x和y最多只能选一个，选x不如选y，这样不仅区间数目不会减少，而且给其他区间留出了更多的位置。接下来，按照bi从小到大的顺序对所有区间排序。会场安排问题先对n个区间按照bi从小到大的顺序排序，如果bi相同，则ai按照从大到小的顺序排序。然后从前往后扫描每个区间，找出所有的符合条件的区间。注意：排序后第一个区间一定会选，因为它的bi最小，它不影响后面区间的选取，而且如果不选此区间，最终求出的区间数目

4、会变少。区间选点问题数轴上有n个闭区间[ai,bi]。取尽量少的点，使得每个区间内都至少有一个点（不同区间内含的点可以是同一个）。【分析】如果区间i内已经有一个点被取到，我们称此区间已经被满足。受上一题的启发，我们先讨论区间包含的情况。由于小区间被满足时大区间一定也被满足。所以在区间包含的情况下，大区间不需要考虑。因此，我们把所有区间按b从小到大排序（b相同时a从大到小排序），则如果出现区间包含的情况，小区间一定排在前面。第一个区间应该选取哪一个点呢？正确的贪心策略是：取最后一个点。如下图。解题思路根据刚才的讨论，所有需要考虑的区间的a也是递增的，我们把它画成上图的形式。如果第一个区间

5、不选最后一个点，而是去中间的，如灰色点，那么把它移动到最后一个点后，被满足的区间增加了，而且原先被满足的区间现在一定被满足。这样才能保证选取的点最少。区间覆盖问题数轴上有n个闭区间[ai,bi]，选择尽量少的区间覆盖一条指定线段[s,t]。【分析】本题的突破口仍然是区间包含和排序扫描，不过要先进行一次预处理。每个区间在[s,t]外的部分都应该预先被切掉，因为它们的存在是毫无意义的。例如要覆盖线段[3,5]，闭区间[0,1]的存在无意义。在预处理后，在相互包含的情况下，小区间显然不应该被考虑。解题思路把各区间按照a从小到大顺序。如果区间1的起点不是s，则无解，即[s,t]无法被完全覆盖（

6、因为其他区间的起点更大，不可能覆盖到s点），否则选择起点在s的最长区间。选择此区间[ai,bi]后，新的起点应该被设置为bi,并且忽略所有区间在bi之前的部分，就像预处理一样。虽然贪心策略比上面的题复杂，但是仍然只需要一次扫描。如下图5所示。s为当前有效起点（此前部分已被覆盖），则应该选择区间2。s穷竭搜索是指将所有的可能性罗列出来，在其中寻找答案的方法。概念：这里，我们主要介绍：深度优先搜索宽度优先搜索基础的“穷竭搜索”深度优先搜索深度优先搜索（DFS，Depth-FirstSearch）是搜索的手段之一。它从某个状态开始，不断地转移状态直到无法转移，然后回退到前一步的状态，继续转移

7、到其他状态，如此不断重复，直至找到最终的解。根据深度优先搜索的特点，采用递归函数实现比较简单。例题给定整数a1,a2,a3,......,an,判断是否可以从中选出若干个数，使他们的和恰好为k。限制条件：1<=n<20-10^8<=ai<=10^8-10^8<=k<=10^8输入：41,2,4,713输出：Yes输入：41,2,4,715输出：No解题过程i=3sum=2i=1sum=1i=1sum=0i=2sum=0i=0sum=0i=3su