枚举、搜索与动态规划试题精讲.ppt
《枚举、搜索与动态规划试题精讲.ppt》由会员分享,可在线阅读,更多相关《枚举、搜索与动态规划试题精讲.ppt(83页珍藏版)》请在装配图网上搜索。
枚举 搜索与动态规划试题精讲 朱全民 枚举 所谓枚举法 指的是从可能的解集合中一一枚举各元素 用题目给定的检验条件判定哪些是无用的 哪些是有用的 能使命题成立 即为其解 一般思路 对命题建立正确的数学模型 根据命题确定的数学模型中各变量的变化范围 即可能解的范围 利用循环语句 条件判断语句逐步求解或证明 枚举法的特点是算法简单 但有时运算量大 对于可能确定解的值域又一时找不到其他更好的算法时可以采用枚举法 枚举法求解的问题必须满足两个条件 可预先确定每个状态的元素个数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 foran an1toankdoif状态 a1 ai an 满足检验条件then输出问题的解 枚举算法的优化枚举算法的时间复杂度可以用状态总数 考察单个状态的耗时来表示 因此优化主要是 减少状态总数 即减少枚举变量和枚举变量的值域 降低单个状态的考察代价优化过程从几个方面考虑 具体讲 提取有效信息 减少重复计算 将原问题化为更小的问题 根据问题的性质进行截枝 引进其他算法 侦探推理 NOIP2003 2 证词中出现的其他话 都不列入逻辑推理的内容 明明所知道的是 他的同学中有N个人始终说假话 其余的人始终说真话 现在 明明需要你帮助他从他同学的话中推断出谁是真正的凶手 请记住 凶手只有一个 要求 判断谁是罪犯 分析 这道题的关键点是 如何能够快速正确实现出来 事实上这道题对编码能力的要求要大于对算法本身的要求 由于这道题的数据范围并不是很大 但需要进行 字符串处理 这种比较麻烦的工作 因此在比赛时就可以采用效率低一些的枚举算法来换取编码上的简单 推荐的算法分为两步 1 预处理每个人的每一句话 并把它们分类处理 2 枚举罪犯和当前星期几 找出所有可能发生的情况 下面我们来逐步细化一下每一步的算法 对于第一步 我们希望的是把一些杂乱的不好处理的 字符串信息 转化为相对比较好处理的信息 为此 我们可以通过把 信息 进行分类的方法使得对于每一类信息 更加方便的处理 即我们可以用一个或者几个变量来表示 由题目描述可以发现语句可分为三类 分析 1 指明i是否是罪犯的语句 2 指明今天是星期d的语句 3 没有意义的语句 不符合格式要求 我们必须要说明的是任何不符合格式要求的语句都将被划分到第三类中去 这样在处理每个语句的时候就必须要考虑该语句是否符合格式要求 通过以上的处理 我们对于每一个语句用几个变量就可以表示了 对于第二步的细化 我们在枚举完罪犯和当前星期几之后 就可以比较方便的判断每一句话的真伪了 这样我们再根据每个人所说的话把人进行分类 1 没说任何一句有意义的话 2 只说真话 3 只说假话 4 既说真话也说假话 分析 需要注意的是 对于第一类人我们既可以把他当成说真话的 也可以把他当成说假话的 而如果第四类人存在的话 那么从他本身就可以推出矛盾了 最后 如果对于罪犯i存在一个d使得当前情况是可能的 我们就说i就是可能的罪犯 时间效率 O MP Day 其中Day Sunday Monday Tuesday Wednesday Thursday Friday Saturday 优化 我们可以发现在对罪犯和当前星期几进行 双重枚举 时 进行了很多重复的操作 于是我们想到 能不能不枚举是当前星期几 这样我们把这类语句与判断罪犯的语句分离 可以先由判断罪犯的语句中确定一部分人肯定说真话 一部分人肯定说假话 剩下的一部分人就要根据他所说的当前星期几的语句来判断了 首先我们假设所有人判断星期的语句不自相矛盾 这样每个人将在判断这类问题里面至多有一个答案 我们便可以统计判断当前是星期d的总人数 于是改进后的算法对于每一个可能的罪犯 先用O p 的时间处理所有的话 再用O Day 的时间枚举星期几 这样 改进后算法的复杂度就是O m p Day 那么我们可不可以再进一步 把算法优化到线性 这里面可以比较明确地告诉大家 是可以做到的 具体的算法类似于上面的按照语句的种类分离语句 只是分离得更细 处理得更复杂 在这里就不做赘述 留给大家思考 现有一个棱长为n的立方体 可以分成n3个1 1 1的单位立方体 每个单位立方体都有一个整数值 n3个单位立方体的数和不会超过longint范围 现在要求在这个立方体找到一个包含完整单位立方体的长方体 使得该长方体内所有单位立方体的数和最大 输入 n 1 n 20 n个n n的数字矩阵 每个数字矩阵代表一层 每个数字代表一个单位立方体的整数值 999 单位立方体的整数值 999输出 长方体的数和1 直译 枚举过程forx1 1tondo 枚举所有可能的平面 forx2 1tondofory1 1tondofory2 1tondoforz1 1tondo 枚举所有可能的上平面和下底面 forz2 1tondo考察状态 x1 y1 z1 x2 y2 z2 立方体问题 考察状态 x1 y1 z1 x2 y2 z2 的任务是计算长方体的体积 并调整最优解 设map为立方体对应的三维矩阵 sum为当前长方体的体积 best为最优解 考察过程如下sum 0 forx x1tox2do 计算长方体的体积 fory y1toy2doforz z1toz2dosum sum map x y z 调整最优解 ifsum bestthenbest sum 这个算法相当粗糙 枚举状态的费用为O n9 2 从减少重复计算入手记录先前考察的结果 在统计长方体2时 只要将长方体1的统计结果加上长方体3就可以了 而不必按上述算法那样重新进行计算 forx1 1tondo 枚举所有可能的水平面 forx2 1tondofory1 1tondofory2 1tondoforz1 1tondo 枚举上平面的z轴坐标 beginsum 0 长方体的体积初始化 forz2 1tondo 枚举下底面的z轴坐标 考察状态 x1 y1 z1 x2 y2 z2 end for 考察过程改为forx x1tox2do 计算长方体的体积 fory y1toy2dosum sum map x y z2 ifsum bestthenbest sum 调整最优解 由于利用了计算出的结果 整个算法的时间复杂度降为O n8 3 提取恰当的信息上述考察实际上求出z轴坐标为z2的平面中矩形 x1 y1 x2 y2 的数和 我们将这个数和记为value a value A value ABCD value B value BC value BD 这就启发我们用另一种方法表示立方体的信息 设rec x y z 表示z轴坐标为z的水平面中矩形 1 1 x y 的数和 z轴坐标为z的水平面中左上角为 x1 y1 右下角为 x2 y2 的矩阵的数和为rec x2 y2 z rec x1 y1 z rec x2 y1 z rec x1 y2 z Rec数组可以在输入数据的同时计算fillchar rec size rec 0 rec数组初始化 forz 1tondo 逐层输入信息 forx 1tondo 逐行输入z平面的信息 beginfory 1tondo 逐列输入z平面上x行的信息 beginread map x y z 输入z平面上 x y 中的数 if x 1 and y 1 计算z平面上以 1 1 为左上角 x y 为右下角的矩形的数和 thenrec 1 1 z map 1 1 z elseify 1thenrec x y z rec x 1 n z map x y z elserec x y z rec x y 1 z map x y z end for readln end for 这样 考察过程就可以改为sum sum rec x2 y2 z2 rec x1 y1 z2 rec x2 y1 z2 rec x1 y2 z2 ifsum bestthenbest sum 时间复杂度降为O n6 如果长方体a的数和是负数 则长方体a的计算结果废弃 考察长方体b a 因为长方体b的数和 长方体b a的数和 长方体a的数和 由于长方体a的数和为负 长方体b a的数和一定大于等于长方体b的数和 由此可见 在累计长方体数和的时候 只要由上而下地枚举长方体下底面的z轴坐标即可 设total z 以z轴坐标为z的平面为下底面的长方体的最大数和 forx1 1tondo 枚举所有可能的子平面 forx2 1tondofory1 1tondofory2 1tondobegintotal 0 长方体以 x1 y1 为左上角 x2 y2 为右下角 的最大数和初始化 forz 1tondo 枚举长方体b下底面的z轴坐标 begintotal max total 0 rec x2 y2 z rec x1 1 y1 1 z rec x2 y1 1 z rec x 1 1 y2 z 计算以z为下底面的长方体b的最大数和 iftotal bestthenbest total 调整最优解 end for end for 这一改进使得考察的状态整数降为O n5 子串 给定一个由自然数串联而成的无限数列1234567891011121314 母串 求任意一个长度不超过200的数列 子串 在其中最早出现的位置 分析 首先 由于母串可无限扩充 显然我们不可能把它全部生成出来 如果边生成母串 边判断所生成的数串是否包含给定的子串 即使是使用字符串处理中高效的KMP算法 耗费的工作量也是巨大的 1121314 先枚举第1位1自然数1之后为2 3 母串中形如123 与子串从第2位开始不符 枚举前2位11自然数11之后为12 13 母串中形如111213 与子串从第3位开始不符 考虑第2位开始12自然数12之前为11 末位与子串第1位相同 之后为13 14 母串中形如1314 与子串匹配 如何优化呢 较好的方法是另辟蹊径 刚才我们枚举的是母串的每一位 不妨换一个角度 从子串着手 先来观察一些片断 12345678910111213141516 很自然得到算法 枚举子串所包含第一个完整的数a的位数La 假设a在母串的第k位出现 kAns k4 跟据Ans a及Ans k计算出位数 总时间复杂度约为O n 3 与之前的不可估量相比有了本质性提高 第4步可通过多种途径求得 这里不作介绍 由于其中牵涉到许多高精度的计算及字符串处理 要求我们细致认真 小结 充分挖掘题目特性是解决本题的关键 得以使枚举这类看似低效率的方法得到较好的运用 同时细致全面的考虑问题也是必不可少的 宽度优先遍历算法框架 从某个未被访问的顶点v出发 依次访问v的各个未曾访问过的邻接点 然后分别从这些邻接点出发广度优先搜索遍历 直到所有已被访问的邻接点都被访问到 PROCbfs v Visite v visted v true Iniqueue q enqueue q v Whilenotempty q do v dlqueue q w FIRSTADJ v Whilew0doifnotvisited w then visite w visited w true enqueue q w w NEXTADJ v w ENDP 神经网络 NOIP2003 1 在兰兰的模型中 神经网络就是一张有向图 图中的节点称为神经元 而且两个神经元之间至多有一条边相连 下图是一个神经元的例子 图中 X1 X3是信息输入渠道 Y1 Y2是信息输出渠道 C1表示神经元目前的状态 Ui是阈值 可视为神经元的一个内在参数 神经元按一定的顺序排列 构成整个神经网络 在兰兰的模型之中 神经网络中的神经无分为几层 称为输入层 输出层 和若干个中间层 每层神经元只向下一层的神经元输出信息 只从上一层神经元接受信息 神经网络 兰兰规定 Ci服从公式 其中n是网络中所有神经元的数目 公式中的Wji 可能为负值 表示连接j号神经元和i号神经元的边的权值 当Ci大于0时 该神经元处于兴奋状态 否则就处于平静状态 当神经元处于兴奋状态时 下一秒它会向其他神经元传送信号 信号的强度为Ci 如此 在输入层神经元被激发之后 整个网络系统就在信息传输的推动下进行运作 现在 给定一个神经网络 及当前输入层神经元的状态 Ci 要求你的程序运算出最后网络输出层的状态 输入格式 第一行是两个整数n 1 n 20 和p 接下来n行 每行两个整数 第i 1行是神经元i最初状态和其阈值 Ui 非输入层的神经元开始时状态必然为0 再下面P行 每行由两个整数i j及一个整数Wij 表示连接神经元i j的边权值为Wij 输出格式 输出包含若干行 每行有两个整数 分别对应一个神经元的编号 及其最后的状态 两个整数间以空格分隔 仅输出最后状态非零的输出层神经元状态 并且按照编号由小到大顺序输出 若输出层的神经元最后状态均为0 则输出NULL 分析 理解问题的第一步就是认真 读题 那么我们先来看一看这个题目涉及的问题 研究一下题目中所给的图的一些性质 可以发现如下特点 1 图中所有的节点都有一个确定的等级 我们记作Level i 2 图中所有的边都是有向的 并且从Level值为i 1的节点指向Level值为i的节点我们不妨将其抽象为 阶段图 更一般地 我们可以发现所有的阶段图都是有向无环的 这样我们可以通过拓扑排序来得到期望的处理节点的顺序 可行算法 由于阶段图的性质使得该图的所有边所连接节点的等级都是相邻的 因此就可以设计出一个基于宽度优先搜索 即BFS 的算法 1 初始时将所有输入层的节点放入队列 2 取出队列中的一个元素 不重复地扩展并处理该节点所发出的边的目标节点 3 如果队列非空 则转向2 4 输出输出层中所有满足条件的节点 但是由于本题在问题描述中并没有明确的给出判断一个节点是否是输入节点 因此需要在算法进行的过程当中额外地考虑一些边界情况的数据 这个过程即便是真实数据没有这样出也是要有的 下面给出的更一般的算法可能会更好的跳过这些边界情况 1 对原图中所有的节点进行一次拓扑排序 2 按照拓扑顺序处理每一个节点 3 输出输出层中所有满足条件的节点 AmazingRobots IOI2003 已知条件 迷宫i i 1 2 每个不会大于20 20 守卫Gi 0 Gi 10 守卫循环移动进行执勤 守卫巡逻的方格数 2 4 求 两个机器人都离开迷宫所用的最少指令数目和离开制指令序列 10000步以内 每一步可以发出的命令可以是N E S W中的一种 有4种选择 对每一步具体发出哪个命令 直接搜索 假设最后结果是T 也就是最少出宫时间 时间复杂度是O 4T 这种方法时间复杂度太高 绝对不可行 5 4和4 4的迷宫第一个机器人的位置是 2 2 第二个机器人的位置是 3 2 当前时间是0 状态 2 2 3 2 0 状态表示 第一个机器人位置 第二个机器认位置 时间 E 2 2 3 2 0 2 3 3 3 1 时间已知 则所有Guard的位置可知 Guard Robot的位置均已知 所以状态可以转移 0时刻 1时刻 2时刻 3时刻 0时刻和2时刻是一样的1时刻和3时刻是一样的 稍加分析 此Guard循环以2为周期循环 状态转移 需要的信息是 Robot位置 Guard位置 PositionofRobot1 2是的作用就是记录Robot位置 Time的作用就是为了计算Guard的位置 状态 positionofRobot1 positionofRobot2 Time Time 10000 这是状态数过多的罪魁祸首 题目说 Guard巡逻经过的格子数只可能是2 3 4 也就是说机器人巡逻周期只能是2 4 6 2 4 6 12 所以第0时刻 12时刻 24时刻 Guard的状态完全相同 12可以看作Guard的周期 Time只要记录当前是第几个周期 因为周期确定了 Guard的位置也完全确定了 0 Time 11 状态数 n n n n 12 12n4 用BFS算法 标志数组判重 时间复杂度O 12n4 n 20完全可以承受 深度优先遍历 从某个未被访问的顶点v出发 深度优先遍历图 直到和v有路径的顶点都访问到 PROCdfs v visite v visited v true w FIRSTADJ v whilew0do ifnotvisited w thendfs w w NEXTADJ v w ENDP 讨论 虫食算问题 给出一个N进制的虫食算式 相同的字母代表相同的数字 不同的字母代表不同的数字 要求求出满足这个算式的唯一一组解 也就是字母和数字的一一对应关系 解决方案1 要求一一对应的关系 就可以枚举这些一一对应的关系 找出符合的一项 这样 关系总数有O N 个 最坏情况下必须枚举所有的关系 并且加以判断 复杂度高达O N N 解决方案2 大体上 从算式最后一位开始模拟运算情况 当可递推时递推 不可递推则枚举 对于一竖列 先处理两个加数 当遇到的字母的值不确定时 则枚举当前位 注意与前面的情况判重 否则不作为处理和 当遇到的字母的值不确定时 可从加数部分确定的值来确定 注意与前面的情况判重和进位 否则看加数部分确定的值是否能得到和部分 注意进位 引出矛盾就回溯 如题目的样例 5ABCEDBDACEEBBAA它最后一位的情况是 D E modN A 对于最后一位只要枚举D E的情况 A则可以由D E的值递推而来 对于倒2位 E C 最后一位进位 modN A E的值可以用前面的结果 枚举C 判断A是否为 D C 最后一位进位 modN 虽然复杂度还是O N 但这种方法限制很多 相当于剪枝 解决方案3 观察题目的条件已经限制得很苛刻 N个变量 每个至少出现一次 而且正好一共有N位的算式 这样就构成了解方程的动机 这N个变量的对应N个未知量 有N位的算式对应N个方程 N个未知量 N个方程 正好可以得到唯一解 这里要注意 对解的要求很严格 必须是0至N 1的每个整数都正好出现一次 但对每位式子的进位关系并不清楚 而进位关系正好影响了方程的常数项 枚举每位是否进位 用时O 2n 因为首位不可能进位 无须枚举 然后 用高斯消元法来解方程 可以在枚举之前先解出方程 枚举的时候再把参数带入 带入求解的复杂度是O n2 解决方案4 在解决方案3的基础上 我们可以对进位的枚举剪枝 观察这个竖列 A B C 若无进位则有AC且B C 若能推导出A A A B为任何不相等字母 则当前的枚举不可行 可用递归枚举 从后向前枚举 处理一个竖列时则加上2个不等式 看是否矛盾 数据结构用邻接矩阵 规定A 若加进不等式A B 要加入所有x x A y B y 枚举x y用O n 2 得时间 再判断是否有x y 森林中的果树 森林中长着一种奇怪的果树 在每个分叉处生长着果实 小虫Nileh和Nixed的食物就是这些果实 他们准备把果树分成两部分 每个虫虫得到各自的一部分 而分果树的方法就是选择一个分叉点 虫虫将他们咬断 自然分叉点上的果实也被扔掉了 这样果树就变成了两个部分 分叉点上面的部分和分叉点下面的部分 注意 每个部分不一定是连在一起的 比如对于右边这颗果树 如果他们咬掉蓝色的果子 那么就被分为红色和黄色的两个部分 被咬掉的果子会被浪费 他们想尽可能的减少浪费 于是虫虫给每个果子一个美味值 对于每个果子 请计算如果咬掉这个果子 它上面部分 下面部分和从树根到这个分叉点的路径中比这个果子更美味的果子各有多少个 分析图例 算法 考虑一个点P 对树进行从左到右的深度优先遍历 那么在A D部分的点会在P之前被访问 B C在之后被访问 同理 从右到左深度优先遍历 那么B D先被访问 A C后被访问 对于求出的这两个序列 可以用nlogn求出序列中每个点之前有多少个点比它大 也就是我们可以求出每个点的Fa Fd Fb Fd Fi表示在i部分中有多少点比固定点大 Fd可以用一遍深度优先遍历求出 最长上升序列 设有整数序列b1 b2 b3 bm 若存在下标i1 i2 i3 in 且bi1 bi2 bi3 bin 则称b1 b2 b3 bm中有长度为n的上升序列bi1 bi2 bi3 bin 求序列b1 b2 b3 bm的最大上升长度n 以及所有长度为n的最大上升子序列个数t输入 整数序列 输出 n t 分析 1 设f i 为前i个数中的最大不下降序列长度 则f i max f j 1 1 j i m bj bi 边界为F 1 1 2 设t i 为前i个数中最长不下降序列的个数 则t i t j 1 j i m bj bi f i f j 1 初始为t i 1当f i n时 将t i 累加举例 1234658109f 123455677t 111111222答案 f 7时 边界为 t 4 进一步 3 求本质不同的最长不下降序列个数有多少个 如 1234658109有 12346810 12345810 1234689 1234589都是本质不同的 但对于1223354f1223354t1112244答案有8个 其中4个1235 4个1234 改进算法 上例显然对于相两个相同的数 重复算了多次因此 我们对算法进行改进 对原序列按b从小到大 当bi bj时按F从大到小 排序 增设Order i 记录新序列中的i个数在原序列中的位置 可见 求t i 时 当f j f j 1 b j b j 1 且Order j 1 Order i 时 便不累加t j 这样就避免了重复 上述算法的时间复杂度为O n2 合唱队形 NOIP2005 3 给出N个人 第i个人的高度为Ai 现在要求找出一个对形 使得从某个人开始 前面的人都呈递增的顺序排列 后面的人呈递减顺序排列找出最长的该队列 解法 动态规划 枚举中间最高的一个人 接着对它的左边求最长上升序列 注意序列中最高的同学不应高过基准 对右边求最长下降序列 同样的 序列中最高的同学不应高过基准 时间复杂度为O n 2 算法实现起来也很简单 接着对这个算法进行分析 我们不难发现 假如还是基于枚举一个同学的话 设Incsq i 表示了1 i的最长上升序列 Decsq i 表示了i n的最长下降序列 那么 Current i Incsq i Decsq i 1 两个数组中i被重复计算了 那么 我们只需要先求好最长上升和下降序列 然后枚举中间最高的同学就可以了 优化 求最长上升序列的经典状态转移方程为 opt i max opt j 1 其中ilist i 我们对状态转移方程稍微做一些修改 opt i max opt i 1 min j rec j list i rec j 记录当前不下降序列的最小值很明显可以看出 在opt i 的寻找j的过程当中 查询序列是单调的 于是可以用二分法 就十分巧妙地在logn的时间内找到指定的j 而问题的总体复杂度为O nlogn 这样 这个问题的算法效率就得到了大幅度的提升 即便n是106 也可以轻松应对 二叉堆 定义n个元素的序列 k1 k2 kn 当且仅当满足ki k2i并且ki k2i 1二叉堆肯定是一颗完全二叉树 堆的构造 第一步 构造一个初始堆第二步 逐步调整该堆 使它符合堆的性质 堆排序算法 PROCshift varr listtype k m integer i k j 2 I x r k key finish falset r k while jr j 1 key thenj j 1 Ifx r j keythenfinish trueElse r i r j i j j 2 I r i tendPPROCheapsort varr listtype Fori n 2 downto1shift r I n Fori ndownto2do r 1 与r i 交换 shift r 1 i 1 endP 合并果子 把合成堆后的每堆的果子仍然看成相对独立的 那么定义timesi等于第i堆果子被合并的次数 ai为第i堆数字权值 则Totalcost 目标求得是min Totalcost 建立一棵二叉树 每堆果子分别为该树的叶节点 一种二叉树形态对应一种合并方案 2堆果子合并则有共同父结点 所以该方案的Totalcost depthi vi i是叶节点 解法是每次取出最小的两个节点 并从节点集合中删除 然后合并这两点后再加入节点集合 重复 直到只剩一个节点 由于每次要取出最小的两个节点 一般做法是每更新一次集合 重新排序 时间是O n2 由于n 10000 不得不采用数据结构 堆进行优化 最大子序和 问题描述输入一个长度为 的整数序列 A1 A2 An 从中找出一段连续的长度不超过M的子序列 使得这个序列的和最大 最大子序和 例如 序列1 3 5 1 2 3 当M 2或3时 S 5 1 6 当M 4时 S 5 1 2 3 7 数据范围 50 的数据N M 1000100 的数据N M 20000 一个简化的问题 序列的最大连续和 输入一个长度为 的整数序列 A1 A2 An 从中找出一段连续的子序列 使得这个序列的和最大 和原问题相比没有M这个序列长度的限制 分析 设F i 表示以第i个数结尾的最大连续和 以第i个数结尾的最大连续和序列 可能存在两种选择 情形一 只包含Ai情形二 包含Ai和以Ai 1结尾的最大连续和序列 动态规划 转移方程 F i max Ai F i 1 Ai 边界 F 1 A1要求的结果为max F i 1 i n 该算法的时间复杂度为O n 一个简化的问题 例一算法一 枚举 设F i 为以Ai结尾长度不超过M的最大子序和 对于每个F i 从1到m枚举k的值 完成Aj的累加和取最大值 该算法的时间复杂度为O n2 原问题初步分析 简化方程 用一个二叉堆来维护S i k 每次求F i 之前的操作如下 算法二 堆 求F i 1 时 求min S i m 1 S i 2 求F i 时 求min S i m S i 1 在堆中删除元素S i m 1 插入元素S i 1 复杂度O 2log2n 从堆中取出当前最小值 复杂度O 1 所以计算的总复杂度为O nlog2n 队列优化 在算法二中 考虑用队列来维护决策值S i k 每次只需要在队首删掉S i m 1 在队尾添加S i 1 但是取最小值操作还是需要O n 时间复杂度的扫描 考察在添加S i 1 的时候 设现在队尾的元素是S k 由于k i 1 所以S k 必然比S i 1 先出队 若此时S i 1 S k 则S k 这个决策永远不会在以后用到 可以将S k 从队尾删除掉 此时队列的尾部形成了一个类似栈的结构 队列优化 同理 若队列中两个元素S i 和S j 若i S j 则我们可以删掉S i 因为S i 永远不会被用到 此时的队列中的元素构成了一个单调递增的序列 即 S1 S2 S3 Sk 算法三 我们来整理在求F i 的时候 用队列维护S i k 所需要的操作 若当前队首元素S x 有x i m为止 若当前队尾元素S k S i 1 则S k 出队 直到S k S i 1 为止 在队尾插入S i 1 取出队列中的最小值 即队首元素 算法三 由于对于求每个F i 的时候 进队和出队的元素不止一个 但是我们可以通过分摊分析得知 每一个元素S i 只进队一次 出队一次 所以队列维护的时间复杂度是O n 而每次求F i 的时候取最小值操作的复杂度是O 1 所以这一步的总复杂度也是O n 综上所述 该算法的总复杂度是O n 小结 在本题的解决过程中 我们首先通过对于一个简化的问题解答 得到了该类问题一般性的解决思路 随后得到了一个O n2 的算法我们通过简化方程 进一步明确和细化了求解目标 运用合理的数据结构 堆 得到了一个O nlog2n 的算法 通过进一步的挖掘求解目标的内涵 寻找内在规律 我们得到只用线性表维护的O n 的算法 过河 NOIP2005 在河上有一座独木桥 一只青蛙想沿着独木桥从河的一侧跳到另一侧 在桥上有一些石子 青蛙很讨厌踩在这些石子上 由于桥的长度和青蛙一次跳过的距离都是正整数 我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点 0 1 L 其中L是桥的长度 坐标为0的点表示桥的起点 坐标为L的点表示桥的终点 青蛙从桥的起点开始 不停的向终点方向跳跃 一次跳跃的距离是S到T之间的任意正整数 包括S T 当青蛙跳到或跳过坐标为L的点时 就算青蛙已经跳出了独木桥 题目给出独木桥的长度L 青蛙跳跃的距离范围S T 桥上石子的位置 你的任务是确定青蛙要想过河 最少需要踩到的石子数 输入文件 输入文件river in的第一行有一个正整数L 1 L 109 表示独木桥的长度 第二行有三个正整数S T M 分别表示青蛙一次跳跃的最小距离 最大距离 及桥上石子的个数 其中1 S T 10 1 M 100 第三行有M个不同的正整数分别表示这M个石子在数轴上的位置 数据保证桥的起点和终点处没有石子 所有相邻的整数之间用一个空格隔开 输出文件 输出文件river out只包括一个整数 表示青蛙过河最少需要踩到的石子数 样例输入 1023523567 样例输出 2 数据规模 对于30 的数据 L 10000 对于全部的数据 L 109 分析 由于不能往回跳 很容易想到用动态规划解决这个题目 设f i 表示跳到第i个点需要踩到的最少石子数 则很容易写出动态规划的状态转移方程 时间复杂度是O L T S 但本题的L高达109 根本无法承受 进一步分析 我们先来考虑这样一个问题 长度为k的一段没有石子的独木桥 判断是否存在一种跳法从一端正好跳到另一端 若S MaxK 都可以从一端正好跳到另一端 题设中1 S T 10 经过简单推导或者程序验证就可以发现 取MaxK 100就能满足所有区间 于是我们可以分两种情况讨论 1 S T时 这时候由于每一步只能按固定步长跳 所以若第i个位置上有石子并且imodS 0那么这个石子就一定要被踩到 这是我们只需要统计石子的位置中哪些是S的倍数即可 复杂度O M 2 SMaxK 2 T 我们就将这段区域缩短成长度为MaxK 2 T 可以证明处理之后的最优值和原先的最优值相同 如上图所示 白色点表示连续的一长段长度大于MaxK 2 T的空地 黑色点表示石子 设原先的最优解中 白色段的第一个被跳到的位置a 最后一个被跳到的位置是b 则在做压缩处理之后 a和b的距离仍然大于MaxK 由上面的结论可知 必存在一种跳法从a正好跳到b 而且不经过任何石子 所以原来的最优解必然在处理之后的最优解解集中 经过这样的压缩处理 独木桥的长度L 最多为 M 1 MaxK 2 T M 大约12000左右 压缩之后再用先前的动态规划求解 复杂度就简化成了O L T S 已经可以在时限内出解了 这样本题就得到了解决 加分二叉树 设一个n个节点的二叉树tree的中序遍历为 l 2 3 n 其中数字1 2 3 n为节点编号 每个节点都有一个分数 均为正整数 记第j个节点的分数为di tree及它的每个子树都有一个加分 任一棵子树subtree 也包含tree本身 的加分计算方法如下 subtree的左子树的加分 subtree的右子树的加分 subtree的根的分数若某个子树为主 规定其加分为1 叶子的加分就是叶节点本身的分数 不考虑它的空 子树 试求一棵符合中序遍历为 1 2 3 n 且加分最高的二叉树tree 要求输出 1 tree的最高加分 2 tree的前序遍历 加分二叉树 输入格式 第1行 一个整数n n 30 为节点个数 第2行 n个用空格隔开的整数 为每个节点的分数 分数 100 输出格式 第1行 一个整数 为最高加分 结果不会超过4 000 000 000 第2行 n个用空格隔开的整数 为该树的前序遍历 输入样例 5571210 输出样例 14531245 分析 如果整棵树的权值最大 必然有左子树的权值最大 右子树的权值也最大 符合最优性原理 可行算法 我们试着写出状态转移方程 f i j max i t j d t f i t 1 f t 1 j 初始 f i i d i 目标 f 1 n 这样 我们可以写出一个动态规划的算法 可以按照状态f i j 中i与j的距离来划分阶段 当然也有其它的划分阶段的办法 先处理掉边界情况 空树和只含有一个节点的树 然后就可以按照阶段自底向上进行动态规划了 最后再递归地输出 注意要保存每次决策 时间复杂度O n3 河流 IOI2005 一颗有N 1个结点的树 树中的每个结点可能会生产出一些产品 这些产品要么就地加工 要有加工厂才行 要么运送到它的父亲结点那儿去 现在在整棵树的根结点处已经有了一个产品加工厂 而且所有的产品最终必须在某个加工厂加工才行 由于运费昂贵 不可能将所有的产品都运送到根节点处加工 现在决定在树中的某些结点新增总共K个加工厂 现在要你选择这K个加工厂的厂址 假设结点i会生产出Wi 吨产品 它的父结点是Pi 而它到它的父结点的路径的长度是Ui 运费的计算是每运送1顿的货物 每单位长度收取1的费用 根节点的编号为0 河流 IOI2005 题设中给出的是一棵多叉树 不便于分析 我们先利用儿子兄弟表示法将多叉树转换成二叉树 儿子兄弟表示法 将一个结点的子孙全都保存在左子树 并且自己的左儿子就是自己在原树中的第一个子结点 将自己的所有兄弟以及兄弟结点所关联的子树都保存在右子树 并且自己的右儿子是自己在原树中拥有同一个父结点的一个兄弟结点 河流 IOI2005 设f i j k 表示在新树中 以i结点为根的子树中 分配k个加工厂 并且离i结点最近的加工厂在j结点 即i节点的货物将被运送到j节点 在这种情况下 i结点及其子树内的所有产品 加工所需要的最小费用 河流 IOI2005 转移方程为 其中 i lch i rch分别表示节点i的左右子树的编号 w i 表示第i个节点产品的吨数 dis i j 表示节点i和节点j的距离 算法的时间复杂度为O n2k2- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 枚举 搜索 动态 规划 试题
装配图网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
关于本文