dp总结.doc

dp 总结 1. 按状态类型分写在前面: 从状态类型分, 并不表示一题只从属于一类。其实一类只是一种状态的表示方法。可以好几种方法组合成一个状态,来解决问题。 . 编号(长度)动态规划共性总结本类的状态是基础的基础, 大部分的动态规划都要用到它, 成为一个维。一般来说,有两种编号的状态: 状态(i) 表示前 i 个元素决策组成的一个状态。状态(i) 表示用到了第 i 个元素,和其他在 1到 i-1 间的元素,决策组成有的一个状态。题库 a) 最长不下降子序列以一元组(i) 作为状态,表示第 i 个作为序列的最后一个点的时候的最长序列。于是很容易想到 O(n2) 得算法。但本题可合理组织状态, 引入一个单调的辅助数组, 利用单调性二分查找, 优化到 O(nlogn) 。关于优化详见优化章。一些问题可将数据有序化,转化成本题。应用: 拦截导弹(NOIP99 Advance 1) 就是原题。 Beautiful People (sgu199) ,要将数据有序化:其中一个权作为第一关键字不下降排列,另一个权作为第二关键字不上升。 Segment (ural 1078) ,将线段的左端点有序化就可以了。 b) LCS 状态(i,j) ,表示第 1 个字符串的第 i 位,与第 2 个字符串的第 j位匹配, 得到的最长的串。若有多个串要 LCS , 则加维, 即几个串就几个维。我也将此题归入路径问题。 c) 花店橱窗布置(IOI99) 见路径问题。 . 区间动态规划共性总结本类问题与下一章的划分问题的决策的分割点无序交集比较大(占本类问题的 30% )。题库 a) 石子合并见划分问题 b) 模版匹配(CEOI01,Patten) 这题特殊的地方是状态的值是一个集合而不是一个数。 c) 不可分解的编码(ACM World Final 2002) d) Electric Path(ural1143) e) 邮局(IOI2000 Day2 1) 若状态表示的思路从第 i 个村庄可以从属于哪个邮局,无最优子结构。转变一个方向:第k 个邮局可以“控制”一个区间的村庄[i,j] 。于是方程就显然了: f(k,i,j)=min{f(k-1,p,i-1)+w(i,j)}(k-1<=p<=i-1) S(i) 为村庄 i 到原点的距离。 w(i,j)=min{k| Sum{|S(k)-S(p)|}(i<=p<=j)}(i<=k<=j) 找到[i,j] 间最好的一个邮局点。不过可以发现 Sum{|S(k)-S(p)| 是单调的,所以取中位数就可以了。即上式中k 的取值范围只有 floor((i+j)/2), ceil((i+j)/2) 两个。 Floor 是下取整。 Ceil 是上取整。这样每次转移时间降到 O(1) 。注意到是区间连续的,即(p,i-1) 和(i, j) 中的 i-1, i 是连续的, 所以空间可以降维: f(i,j) 表示放前i 个邮局到前j 个村庄的最优值。 f(i,j)=min{f(i-1,p-1)+w(p,j)}(i-1<=p<=j-1} e(i,j) 为当 f(i,j) 到达最优值时的 p. 通过证明四边形不等式,得到 e(i,j)<=e(i,j+1)<=e(i+1,j+1) 决策数量又少了一个数量级。 . 坐标动态规划共性总结之后的一些问题, 状态是由坐标维与其他的维组成。本类与划分问题(是2 维或多维的坐标系的划分) 与路径问题的交集占本类问题中大多数。题库 a) 棋盘分割(NOI99 4) 主要是将公式变形,变形后的公式很容易看出方程。状态是由 2 个坐标组成的 4 元组(x1,y1)(x2,y2) ,表示一个子棋盘。这有点像之前的区间动态规划,只不过是将 1 维转 2 维。后见路径问题。 . 数轴动态规划共性总结题库 a) 01 背包应用: 装箱问题( NOIP01 Trade 4) 就是原题。值币分割可利用方程的性质,空间降 1 维。币值可重复的值币分割(pku1742, Problem F LouTianCheng ’s Contest in POJ) 2008-11-5 02:00 回复 RAMBOO 4 位粉丝 2楼使用左右法在定位上加速。另给状态加一个属性 last, 记录上一次剩下的可用的同币值硬币数(利用了当前转移是唯一前驱的特点)。 b) 取火柴问题(sgu153 Playing with matches) c) Stone Pile(ural1005 Stone Pile) d) 公路巡逻(CTSC2000) . 5. 树型动态规划共性总结 1) 动态规划的顺序一般按照后序遍历的顺序, 即处理完儿子再处理当前节点, 才符合树的子结构的性质。 2) 多叉树转换为二叉树由于要分配附加