浅析NOIp范围内的DP算法

1、浅析NOIP范围内的DP算法深圳市龙城高级中学刘伟潜1.NOIP中,DP的出题方向近年来,DP已成为NOIP中的“必考”项目,在06年的提高组题目中,甚至出现了两题DP(且该年分数线约为130分,DP的重要性可见一斑。由于NOIP的难度所限,所出的DP基本上都是一些典型的模型加以稍许改编。如下:2003:加分二叉树:树型动态规划(区间类。2004:合唱队形:双向最长不降(升序列。2005:过河:需压缩空间的线性动态规划。2006:能量项链:环状的合并类;金明的预算:需分类以取消后效性的01背包问题。2007:矩阵取数:需高精度的区间类动态规划。由此可见,NOIP在DP一块上的出题思路基本上是:

2、不出刁钻的,罕见的动态规划类型,模式通常较易识别,但添加了部分新难点,以增加题目的区分度。这也就要求我们在复习DP算法时,集中注意力在一些典型的模型,以及了解其本质,才能拿下稍作变形的真题。2.一些经典的DP模型一道DP往往可以通过多种方式去做,所以以下分类并不完全准确,是相对而言的。大家不要死记某种类型,而应把握该类题型的本质和共性。1不降(升序列类&线性类不降序列问题相信大家都做过。它的特点是线性递推,通常以某一结点为状态,转移是由前往后线性遍历。典型题目有导弹拦截和过河。由于大家都很熟悉了,加上今年来NOIP 出了好几回,这里不做多说。特别留意:2背包类特别留意:1.要保证无后效

3、性,遇到设置后效性的题目可以分类处理(如金明的预算。2.如有多维,且维数太多,则考虑降低每次循环的次数或考虑其他思路。3.在实现算法时,如果状态转移只在相邻两三个阶段间发生,则可用动态数组,可以减少空间需要。4.背包类题目也可以出得很隐蔽,比如多米诺骨牌问题,重要的是抽取模型。5.需特别注意解数组的初始值设定,弄清楚解为0与无解的区别,常把初始值设为无穷小,也可都设为0,再在引用时判断是否是无解。3路径类路径类的典型例题有三角取数和花店橱窗布置。其特点是决策是“左走”,“右走”或“直走”。这类题目是十分典型的DP模型,但已有几年没出了,需留意。特别留意:1.注意边界的设置。2.实现算法时可用动

4、态数组,减少空间。3.若题目设置“时间”概念,可能需要加维。4区间&合并类区间类问题可以看做一个连续的大区间被分割成若干个有重叠的小区间,再从中选择最优解,而选择的依据就是转移方程。由于这种题长度为L的区间需要引用到长度不足L的区间的结果,所以常以长度作为阶段,起始位置为状态。合并类是在区间类基础上,以最佳合并为选择依据的一类题目。这类题目分别出在了06年和07年考题上能量项链和矩阵取数,今年再出的可能性相对不大,但也不可轻视。特别留意:1.如遇环状模型,可从任意一结点断开,在后方补足,使之成为线性。2.转移方程中,可能有需要预处理的内容,或用贪心算法。5树型树型动态规划,就是指建立在

5、树这个数据结构上的动态规划。它的特点是以单个结点为状态,转移方程有该结点的孩子参与,计算过程自下往上进行。上一次出此类题目是5年前,说不准今年就会出。它的典型例题有选课和战略游戏。特别留意:1.掌握好树的读入方式,以及多叉树变二叉树的方式。6布尔型这是一种相对少见的类型,其实还是属于背包类或线性类,只是它的最优值数组是布尔类型,所以我将其独立为一类。它的特点是最优解数组的类型为布尔类型,转移方程为逻辑运算,实际的问题最优解藏在状态之中。典型的题有砝码问题和取余问题特别留意:1.使用前,要论证可以使用此类DP。2.取余类问题中,状态设置应为-(m-1.(m-1或0.(m-1。7坐标类这种类型也很

6、少见,而且难度通常较大,不必过于关注。其特点是:在平面或立体内,以点坐标或相应矩形为状态。典型问题有棋盘分割和奶牛浴场。特别留意:1.此类题目往往根据几何关系或数学知识推断出转移方程。8集合状态类这种类型也不多见,但特点很突出。它往往具有多个状态维数,有时多达5,6个,而且决策与若干个状态组成一个整体,修改最值时一同更新。典型例题有购物和快餐问题。特别留意:1.确定使用此类DP后,大胆增设状态维数。2.要找出切实可行的转移方程和算法实现方式。9字符串类字符串类问题也不是一个专门的DP类型,这里专指一些利用到字符串特点的DP问题,特别留意:1.要确定最优解的状态的所有可能性。2.多数时候此类问题

7、还是属于线性类问题,需要结合线性类的特点设计算法。3.可留意一下KMP算法。4.可留意一下回文字一类题目。3.NOIP可能会给模型增加的难度1非线性数据类型在数据类型方面,NOIP最可能增添的难度是出环状和树状。1树状对于树状,我们通常可以用树型DP解决。需留意的是,有些看似树型DP的题,其实可能是区间类DP,如03年的加分二叉树。另外,树的输入方式有很多种,我们必须熟悉如何恰当保存树的数据,否则即便会做DP也拿不了分。2环状对于环状,我们有两种处理方法将其破坏成链:1.确定某结点为起点,枚举该结点状态,每次枚举后DP求解,记录起点为该状态下得到的最优解。最后将各种可能的最优解筛选出问题的最优

8、解。此类方法适用于线性DP和路径型DP。2.对于长度为n的环,任意选取一点为起点,由起点开始得到一条长度为n的链,将前面n-1长度的链复制并转移到链的末端,相当于将两条同样的链首尾相接。由此,环的任意一种单向遍历方式都可以在这个长度为2n-1的链中实现。此类方法适用于区间类DP。从本质上讲,这两种处理方式是完全一样的,既枚举起点的位置或状态,利用DP求解。需要留意的是,这种条件下的最优值的位置往往要特别考虑的。2结合其他算法1贪心DP和贪心结合的例子很常见,有以下两种:1.通过贪心确定转移方程,也可以作为预处理部分。例题为邮局。2.通过贪心确定最优解的上限或下限,从而减少循环量,在大规模数据时

9、很有效。例题为快餐问题。2搜索搜索和DP的结合,可以体现在两方面:1.记忆化搜索所谓“记忆化搜索”就是在传统的搜索过程中,加入DP的“保留子问题最优解”思想,提高时间效率。从框架上讲,还是搜索算法,这里不作讨论。2.搜索中的局部进行DP求解在搜索过程中,某个局部可能用到DP进行求解。例题为邮票面值设计。3字符串处理、高精度、排序、求质数等这几样都是基础算法,可作为DP的预处理,这里不多做叙述。3提出其他任务1输出最优方案这是很常见的一种题目要求,它不仅要求我们求出最优值的大小,还要确定与之对应的每个决策。通常有两个方法解决:1.增添记录每次决策的数组M。在每次做决策时,M中对应的状态也保留一个

10、代表该决策的值。如01背包中,某个背包取或不取,M中对应的值为1或0。在得出最优解后,正向遍历M(构建队列或逆向遍历M(构建栈,从而输出最优方案。2.一些题目的性质决定,在得出最优解后,可以通过贪心输出最优方案。如书的复制前一种方法具有普遍性,在时空允许下绝大部分DP题目适用。后一种题目在小范围内适用,但其编程复杂度和时空复杂度都相当理想。2求前k优解(方案或第k优解(方案此问题可通过增设状态维数解决。在最优解数组中增加一维p表示同样状态下的第p 优解,显然在DP过程中,只需保留每个状态的前k优解就足够。在状态转移时,算出新状态的前k个最优解,依次保存。需要注意的是,每一种可以得出新状态的前k

11、个最优解的情况都要考虑到。另外,题目可能问前k个最优解(数字一样时当一种解,中间的策略不用考虑,也可能问前k个最优方案(不仅数字一样,而且策略也一样,做题时要加以区分。3求最优方案的个数这个问题可以用1和2中的思想共同解决。增设数组C,表示一定状态下的最优方案的个数,在状态转移时,小心叠加即可。4同时问两类最优值4增设小范围的后效性如果你看到一道很熟悉的DP题,但又发现它在小范围内有后效性,那么也许在进行简单处理后，这题依然可以用 DP 求解。 这类题目类型有 2： 1）具后效性的状态与它控制的状态成主次关系 具后效性的状态与它控制的状态成主次关系 典型的例子为金明的预算方案 若干状态被一个状态控制， 金明的预算方案， 那么可以把这几个状态连同 金明的预算方案 控制它的状态作为一个类，将题目的所有状态分成若干个类进行处理。每个类中，如果要选 择当中的次级状态， 必须先选中它所依赖的状态。 也可以理解成将题目各状态转化为树的形 式进行 DP，若要选择一个结点，必先选择它的父母，而兄弟间是没联系的。 2）具后效性的状态与它控制的状态成并列关系 具后效性的状态与它控制的状态成并列关系 5）多进程问题 多进程问题 不能多次 DP，必须增设状态维数。 6）大规模数据 大规模数据 1）宏观上优化 宏观上优化 状态划分能否降维