1
浅析 NOIP 范围内的 DP 算法
2009-08-12 10:03
一、NOIP 中，DP 的出题方向
近年来，DP 已成为 NOIP 中的“必考”项目，在 06 年的提高组题目中，甚至出现了两
题 DP（且该年分数线约为 130 分），DP 的重要性可见一斑。
由于 NOIP 的难度所限，所出的 DP 基本上都是一些典型的模型加以稍许改编。如下：
2003：加分二叉树：树型动态规划（区间类）。
2004：合唱队形：双向最长不降（升）序列。
2005：过河：需压缩空间的线性动态规划。
2006：能量项链：环状的合并类；金明的预算：需分类以取消后效性的 01 背包问题。
2007：矩阵取数：需高精度的区间类动态规划。
由此可见，NOIP 在 DP 一块上的出题思路基本上是：不出刁钻的，罕见的动态规划
类型，模式通常较易识别，但添加了部分新难点，以增加题目的区分度。这也就要求我
们在复习 DP 算法时，集中注意力在一些典型的模型，以及了解其本质，才能拿下稍作
变形的真题。
二、一些经典的 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.在实现算法时，如果状态转移只在相邻两三个阶段间发生，则可用动态数组，可以减少
空间需要。
