tceic.com
学霸学习网 这下你爽了
赞助商链接
当前位置:首页 >> IT/计算机 >>

NOIP范围内的DP算法


浅析 NOIP 范围内的 DP 算法
刘伟潜

1.NOIP 中,DP 的出题方向
近年来,DP 已成为 NOIP 中的“必考”项目,在 06 年的提高组题目中,甚至出现了两 题 DP(且该年分数线约为 130 分) ,DP 的重要性可见一斑。 由于 NOIP 的难度所限,所出的 DP 基本上都是一些典型的模型加以稍许改编。 如下: 2003:加分二叉树:树型动态规划(区间类) 。 2004:合唱队形:双向 双向最长不降(升)序列。 双向 2005:过河:需压缩空间 需压缩空间的线性动态规划。 需压缩空间 2006:能量项链:环状 环状的合并类;金明的预算:需分类 需分类以取消后效性的 01 背包问题。 环状 需分类 2007:矩阵取数:需高精度 需高精度的区间类动态规划。 需高精度 2008:传纸条:路径类 由此可见,NOIP 在 DP 一块上的出题思路基本上是:不出刁钻的,罕见的动态规划类 型,模式通常较易识别,但添加了部分新难点,以增加题目的区分度。这也就要求我们在复 习 DP 算法时, 集中注意力在一些典型的模型, 以及了解其本质, 才能拿下稍作变形的真题。

2.一些经典的 DP 模型
一道 DP 往往可以通过多种方式去做,所以以下分类并不完全准确,是相对而言的。大 家不要死记某种类型,而应把握该类题型的本质 共性 本质和共性 本质 共性。

1)不降(升)序列类&线性类 不降( 线性类 不降 序列类 线性
不降序列问题相信大家都做过。它的特点是线性递推,通常以某一结点为状态,转移是 由前往后线性遍历。典型题目有导弹拦截 过河。由于大家都很熟悉了,加上今年来 NOIP 导弹拦截和过河 导弹拦截 过河。 出了好几回,这里不做多说。 特别留意: 1.不降(升)序列的 O(nlogn)算法。 (http://fqq11679.blog.hexun.com/21632261_d.html) 2.不降(升)序列中的方案个数。 (http://blog.sina.com.cn/s/blog_4d801ace01000bj7.Html) 3.对于大数据可能需根据实际进行压缩,主要通过转移方程决定。 (*可能用到“维护” 思想,http://www.rqnoj.cn/Problem_Show.asp?PID=386) 4.线 性 类 题 目 可 以 隐 藏 得 很 深 , 构 建 模 型 时 需 多 加 留 意 能 否 用 线 性 DP 做 。 (http://live.cqfls.cn/ShowArticle.asp?ArticleID=709)

2)背包类 背包类
背包类问题也是大家常见的类型。 它的特点是以前几样物品组成的集合为状态, 决策也 很明显——“取”与“不取” 。背包类问题的变形十分多,这里强烈建议大家抽时间去看著 名的《背包九讲 》 ,里面写得相当详尽,掌握里面的内容后,背包类基本上不用担忧了。 《 背包九讲》 (http://www.concretevitamin.com.cn/informatics/Pack/Index.html) 特别留意: 1.要保证无后效性,遇到设置后效性的题目可以分类处理(如金明的预算) 。 2.如有多维,且维数太多,则考虑降低每次循环的次数或考虑其他思路。 3.在实现算法时,如果状态转移只在相邻两三个阶段间发生,则可用动态数组,可以减 少空间需要。 4.背包类题目也可以出得很隐蔽,比如多米诺骨牌问题,重要的是抽取模型。 (见 http://hi.baidu.com/rangemq/blog/item/9a6b5360c5e76145eaf8f842.html) 5.需特别注意解数组的初始值设定,弄清楚解为 0 与无解的区别,常把初始值设为无穷 小,也可都设为 0,再在引用时判断是否是无解。 3)路径类 路径类的典型例题有三角取数 花店橱窗布置 其特点是决策是 三角取数和花店橱窗布置 “左走” , “右走” “直 或 三角取数 花店橱窗布置。 走” 。这类题目是十分典型的 DP 模型,但已有几年没出了,需留意。 特别留意: 1.注意边界的设置。 2.实现算法时可用动态数组,减少空间。 3.若题目设置“时间”概念,可能需要加维。

4)区间 合并类 区间&合并类 区间
区间类问题可以看做一个连续的大区间被分割成若干个有重叠的小区间, 再从中选择最 优解,而选择的依据就是转移方程。由于这种题长度为 L 的区间需要引用到长度不足 L 的 区间的结果,所以常以长度作为阶段,起始位置为状态。合并类是在区间类基础上,以最佳 合并为选择依据的一类题目。 这类题目分别出在了 06 年和 07 年考题上——能量项链 矩阵 能量项链和矩阵 能量项链 取数,今年再出的可能性相对不大,但也不可轻视。 取数 特别留意: 1.如遇环状模型,可从任意一结点断开,在后方补足,使之成为线性。 (http://www.rqnoj.cn/Problem_Show.asp?PID=5) 2.转移方程中,可能有需要预处理的内容,或用贪心算法。 (http://www.vijos.cn/Problem_Show.asp?id=1242)

5)树型 树型

树型动态规划, 就是指建立在树这个数据结构上的动态规划。 它的特点是以单个结点为 状态, 转移方程有该结点的孩子参与, 计算过程自下往上进行。 上一次出此类题目是 5 年前, 说不准今年就会出。它的典型例题有选课 战略游戏 选课和战略游戏 选课 战略游戏。 (http://www.vijos.cn/Problem_Show.asp?id=1180)

特别留意: 1.掌握好树的读入方式,以及多叉树变二叉树的方式。 2.因为树的特殊结构,经常要分类讨论一个结点在做决策时的各种可能性,需要小心处 理,考虑周全。 (http://www.rqnoj.cn/Problem_Show.asp?PID=387)

6)布尔型 布尔型
这是一种相对少见的类型, 其实还是属于背包类或线性类, 只是它的最优值数组是布尔 类型,所以我将其独立为一类。它的特点是最优解数组的类型为布尔类型,转移方程为逻辑 运算,实际的问题最优解藏在状态之中。典型的题有砝码问题 取余问题 砝码问题和取余问题 砝码问题 (http://www.vijos.cn/Test_Problem_Show.asp?testid=1032&id=1455) 特别留意: 1.使用前,要论证可以使用此类 DP。 2.取余类问题中,状态设置应为[-(m-1)..(m-1)]或[0..(m-1)]。

7)坐标类 坐标类
这种类型也很少见,而且难度通常较大,不必过于关注。其特点是:在平面或立体内, 以点坐标或相应矩形为状态。典型问题有棋盘分割 奶牛浴场 棋盘分割和奶牛浴场 棋盘分割 奶牛浴场。 特别留意: 1.此类题目往往根据几何关系或数学知识推断出转移方程。

8)集合状态类 集合状态类
这种类型也不多见,但特点很突出。它往往具有多个状态维数,有时多达 5,6 个,而 且决策与若干个状态组成一个整体,修改最值时一同更新。典型例题有购物 快餐问题 购物和快餐问题 购物 快餐问题。 特别留意: 1.确定使用此类 DP 后,大胆增设状态维数。 2.要找出切实可行的转移方程和算法实现方式。

9)字符串类 字符串类
字符串类问题也不是一个专门的 DP 类型, 这里专指一些利用到字符串特点的 DP 问题, 如最长公共子序列 调整队形 它往往是两个字符串按一定的规则匹配, 最长公共子序列和调整队形 从而得到一系列最 最长公共子序列 调整队形。 优解。 常用的方法是以一个字符串中的一个字符去匹配另一个字符串的前面若干个字符构成

的子串。 (http://oi.tju.edu.cn/problem/view/1006.html) 特别留意: 1.要确定最优解的状态的所有可能性。 2.多数时候此类问题还是属于线性类问题,需要结合线性类的特点设计算法。 3.可留意一下 KMP 算法。 4.可留意一下回文字一类题目。

3.NOIP 可能会给模型增加的难度
1)非线性数据类型 非线性数据类型
在数据类型方面,NOIP 最可能增添的难度是出环状和树状。 1)树状 树状 对于树状,我们通常可以用树型 DP 解决。需留意的是,有些看似树型 DP 的题,其实 可能是区间类 DP,如 03 年的加分二叉树。另外,树的输入方式有很多种,我们必须熟悉如 何恰当保存树的数据,否则即便会做 DP 也拿不了分。 2)环状 环状 对于环状,我们有两种处理方法将其破坏成链: 1.确定某结点为起点,枚举该结点状态,每次枚举后 DP 求解,记录起点为该状态下得 到的最优解。最后将各种可能的最优解筛选出问题的最优解。此类方法适用于线性 DP 和路 径型 DP。 2.对于长度为 n 的环,任意选取一点为起点,由起点开始得到一条长度为 n 的链,将前 面 n-1 长度的链复制并转移到链的末端,相当于将两条同样的链首尾相接。由此,环的任意 一种单向遍历方式都可以在这个长度为 2n-1 的链中实现。此类方法适用于区间类 DP。 从本质上讲, 这两种处理方式是完全一样的, 既枚举起点的位置或状态, 利用 DP 求解。 需要留意的是,这种条件下的最优值的位置往往要特别考虑的。

2)结合其他算法 结合其他算法
1)贪心 贪心 DP 和贪心结合的例子很常见,有以下两种: 1.通过贪心确定转移方程,也可以作为预处理部分。例题为邮局 邮局。 邮局 (http://www.vijos.cn/Problem_Show.asp?id=1242) 2.通过贪心确定最优解的上限或下限,从而减少循环量,在大规模数据时很有效。例题 为快餐问题 快餐问题。 快餐问题 2)搜索 搜索 搜索和 DP 的结合,可以体现在两方面: 1.记忆化搜索 所谓“记忆化搜索”就是在传统的搜索过程中,加入 DP 的“保留子问题最优解”思想,

提高时间效率。从框架上讲,还是搜索算法,这里不作讨论。 2.搜索中的局部进行 DP 求解 在搜索过程中,某个局部可能用到 DP 进行求解。例题为邮票面值设计 邮票面值设计。 邮票面值设计 (http://www.vijos.cn/Problem_Show.asp?id=1179) 3)字符串处理、高精度、排序、求质数等 字符串处理、高精度、排序、 字符串处理 这几样都是基础算法,可作为 DP 的预处理,这里不多做叙述。

3)提出其他任务 提出其他任务
1)输出最优方案 输出最优方案 这是很常见的一种题目要求, 它不仅要求我们求出最优值的大小, 还要确定与之对应的 每个决策。通常有两个方法解决: 1.增添记录每次决策的数组 M。 在每次做决策时, 中对应的状态也保留一个代表该决 M 策的值。如 01 背包中,某个背包取或不取,M 中对应的值为 1 或 0。在得出最优解后,正 向遍历 M(构建队列)或逆向遍历 M(构建栈) ,从而输出最优方案。 2.一些题目的性质决定,在得出最优解后,可以通过贪心输出最优方案。如书的复制 书的复制 (http://www.rqnoj.cn/Problem_Show.asp?PID=349) 前一种方法具有普遍性,在时空允许下绝大部分 DP 题目适用。后一种题目在小范围内 适用,但其编程复杂度和时空复杂度都相当理想。 2)求前 k 优解(方案)或第 k 优解(方案) 求前 优解(方案) 优解(方案) 此问题可通过增设状态维数解决。在最优解数组中增加一维 p 表示同样状态下的第 p 优解,显然在 DP 过程中,只需保留每个状态的前 k 优解就足够。在状态转移时,算出新状 态的前 k 个最优解,依次保存。需要注意的是,每一种可以得出新状态的前 k 个最优解的情 况都要考虑到。另外,题目可能问前 k 个最优解(数字一样时当一种解,中间的策略不用考 虑) ,也可能问前 k 个最优方案(不仅数字一样,而且策略也一样) ,做题时要加以区分。 3)求最优方案的个数 求最优方案的个数 这个问题可以用 1)和 2)中的思想共同解决。增设数组 C,表示一定状态下的最优方 案的个数,在状态转移时,小心叠加即可。 4)同时问两类最优值 同时问两类最优值 有时题目会要求两类最优值 A 和 B。遇到这样的问题,要分清楚其依赖关系,比如题 目实际要求输出 A 的最优解,以及在 A 最优的情况,B 的最优解。如此一来我们依然以 B 为状态,A 为实际的最优解进行 DP 求解。同时我们增设一个数组 Q,在计算 A 的过程中, 在保证 A 最优的情况下,保存最优的 B;遇到更优的 A 时,也更新 B 的最优解。例题为找 找 GF。 (http://www.rqnoj.cn/Problem_Show.asp?PID=57)

4)增设小范围的后效性 增设小范围的后效性
如果你看到一道很熟悉的 DP 题,但又发现它在小范围内有后效性,那么也许在进行简 单处理后,这题依然可以用 DP 求解。 这类题目类型有 2:

1)具后效性的状态与它控制的状态成主次关系 具后效性的状态与它控制的状态成主次关系 典型的例子为金明的预算方案 若干状态被一个状态控制, 金明的预算方案, 那么可以把这几个状态连同 金明的预算方案 控制它的状态作为一个类,将题目的所有状态分成若干个类进行处理。每个类中,如果要选 择当中的次级状态, 必须先选中它所依赖的状态。 也可以理解成将题目各状态转化为树的形 式进行 DP,若要选择一个结点,必先选择它的父母,而兄弟间是没联系的。 2)具后效性的状态与它控制的状态成并列关系 具后效性的状态与它控制的状态成并列关系

5)多进程问题 多进程问题
不能多次 DP,必须增设状态维数。

6)大规模数据 大规模数据
1)宏观上优化 宏观上优化 状态划分能否降维,状态转移能否贪心或预处理,能否贪心求上限下限,能否加大空间 以换取时间,能否压缩储存空间如使用动态数组,能否采用双向动态规划(不推荐) 。 2)微观上优化 微观上优化 能否在每次循环时尽可能降低循环次数, 能否通过对选项排序减少运算量, 能否剔除不 可能的选择(包括状态和答案) 。 如果以上优化仍未能使 DP 算法达到可行程度, 则要考虑题目是否用贪心策略或递推策 略。



推荐相关:

NOIP提高组 01-12 DP题目

NOIP 提高组 01-12 DP 题目整理:山西大学附属中学...将上题的数据范围改成 6<n<=200000,2<=k<=...家里购置的新房就要领钥匙了, 新房里有一间金明自己...


NOIP模板代码(C++)_图文

1 dp[i-1][j]+a[i](把第 i 个元素包含在最后一个子段内) 2 dp[i-...NOIP复习资料(C++版) 218页 2下载券 NOIP常用算法 11页 免费 数论算法模板...

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com