acm基础算法入门
32页1、ACM基础算法入门,.基础动态规划 .基础的“穷竭搜索” .贪心的三种区间问题 .数论那些事 .二分的另类法,引言,算法简单但思想及其重要 介绍的算法都堪称为经典中的经典,基础动态规划,多阶段决策过程最优化的数学方法 三要素: -阶段 -决策 -状态,动态规划的适用范围,最优子结构(最优化原理) 当前状态依赖于前面的状态得到,是前面状态的完美总结 无后效性(不成环),经典模型,数塔模型 背包问题 区间最大和模型 最长非降子序列模型 最长公共子序列 数字归并(区间dp) 旅行商问题(状态压缩),求解从顶到下经过节点的最大值是多少,解题思路,列状态 v I j 表示走到第i层的第j个节点的最大值 分阶段 每一个层就是一个阶段 状态转移方程(决策) V i-1 j += V I j v I j + 1 ? V I j : v I j + 1 ;,单调递增非降子序列,给定一整型数列a1,a2.,an(0n=100000),找出单调递增最长子序列,并求出其长度。 如:1 9 10 5 11 2 13的最长单调递增子序列是1 9 10 11 13,长度为5。,解题思路,定义状态 dp【i】以i为结
2、束节点最长单调子序列长度 阶段 每一个点选择过程即阶段 转移方程: Dp【i】= max(dp【1(i-1)】) + 1 想想有没有更好的方法?,dp总结,模型匹配法 三要素法 先确定阶段(数塔问题) 先确定状态(一般题目都是) 先确定决策(背包问题),贪心的三种区间问题,选择不相交区间 区间选点 区间覆盖,选择不相交区间,数轴上有n个开区间(ai,bi),选择尽量多个区间, 使得这些区间两两没有公共点。,【分析】 首先明确一个问题:假设有两个区间x,y,区间x完全 包含y。那么,选x是不划算的,因为x和y最多只能选一个, 选x不如选y,这样不仅区间数目不会减少,而且给其他区 间留出了更多的位置。接下来,按照bi从小到大的顺序对 所有区间排序。,会场安排问题,先对n个区间按照bi从小到大的顺序排序,如果 bi相同,则ai按照从大到小的顺序排序。然后从前往后 扫描每个区间,找出所有的符合条件的区间。 注意:排序后第一个区间一定会选,因为它的bi最小, 它不影响后面区间的选取,而且如果不选此区间,最终 求出的区间数目会变少。,区间选点问题,数轴上有n个闭区间ai, bi。取尽量少的点,使得
3、每个 区间内都至少有一个点(不同区间内含的点可以是同一个)。,【分析】 如果区间i内已经有一个点被取到,我们称此区间已经被 满足。受上一题的启发,我们先讨论区间包含的情况。由于 小区间被满足时大区间一定也被满足。所以在区间包含的情 况下,大区间不需要考虑。 因此,我们把所有区间按b从小到大排序(b相同时a从 大到小排序),则如果出现区间包含的情况,小区间一定排 在前面。第一个区间应该选取哪一个点呢?正确的贪心策略 是:取最后一个点。如下图。,解题思路,根据刚才的讨论,所有需要考虑的区间的a也是递增的, 我们把它画成上图的形式。如果第一个区间不选最后一个点, 而是去中间的,如灰色点,那么把它移动到最后一个点后, 被满足的区间增加了,而且原先被满足的区间现在一定被满 足。这样才能保证选取的点最少。,区间覆盖问题,数轴上有n个闭区间ai, bi,选择尽量少的区间覆盖 一条指定线段s, t。,【分析】 本题的突破口仍然是区间包含和排序扫描,不过要先 进行一次预处理。每个区间在s,t外的部分都应该预先被切 掉,因为它们的存在是毫无意义的。例如要覆盖线段3,5, 闭区间0,1的存在无意义。在预处理
4、后,在相互包含的情况 下,小区间显然不应该被考虑。,解题思路,把各区间按照a从小到大顺序。如果区间1的起点不是s, 则无解,即s,t无法被完全覆盖(因为其他区间的起点更大, 不可能覆盖到s点),否则选择起点在s的最长区间。选择此 区间ai,bi后,新的起点应该被设置为bi,并且忽略所有区间在 bi之前的部分,就像预处理一样。虽然贪心策略比上面的题 复杂,但是仍然只需要一次扫描。如下图5所示。s为当前有 效起点(此前部分已被覆盖),则应该选择区间2。,s,穷竭搜索是指将所有的可能性罗列出来,在其中寻找答案的方法。,概念:,这里,我们主要介绍:,深度优先搜索,宽度优先搜索,基础的“穷竭搜索”,深度优先搜索,深度优先搜索(DFS,Depth-First Search)是搜索的手段之一。 它从某个状态开始,不断地转移状态直到无法转移,然后回退到前一步的状态,继续转移到其他状态,如此不断重复,直至找到最终的解。 根据深度优先搜索的特点,采用递归函数实现比较简单。,例题,给定整数 a1,a2,a3,an, 判断是否可以从中选出若干个数,使他们的和恰好为k。 限制条件: 1=n20 -108=ai=
《acm基础算法入门》由会员简****9分享,可在线阅读,更多相关《acm基础算法入门》请在金锄头文库上搜索。
2019年自贡市清华园学校高考生物简单题专项训练(含解析)
2019年秋季石油大学现代应用文写作网考练习试题+在线作业答案
2019年信宏中学高考生物简单题专项训练(含解析)
2019年莲塘中学高考生物简单题专项训练(含解析)
2019年宜阳县二中高考生物简单题专项训练(含解析)
2019年宁波神舟学校高考生物简单题专项训练(含解析)
2019年谢通门县中学高考生物简单题专项训练(含解析)
2019年前埔中学高考生物简单题专项训练(含解析)
2018年二级建造师公路工程实务重点考点总结
2018年一级建造师水利水电实务考点重点
2019年一级建造师市政实务案例考点
概率论与数理统计第二版谢永钦课后答案
空间向量求角度与距离10种题型归类 (解析版)2023-2024学年高二数学上学期期中期末复习讲练测(人教A版2019选择性必修第一册)
中医综合模拟试卷348
2011年3000名教师及特岗招考《计算机基础》复习题
2019年槎水中学高考生物简单题专项训练(含解析)
2009年9 月全国计算机等级考试二级笔试试卷
2019年宣城市第四中学高考生物简单题专项训练(含解析)
中医综合模拟试卷333
2019年安全知识竞赛题库2
2024-01-31 15页
2024-01-31 21页
2024-01-31 37页
2024-01-31 30页
2024-01-31 22页
2024-01-31 48页
2024-01-31 32页
2024-01-31 40页
2024-01-31 31页
2024-01-31 20页