《动态规划总结》由会员分享，可在线阅读，更多相关《动态规划总结（8页珍藏版）》请在金锄头文库上搜索。
1、动态规划by Amber1. 按状态类型分与在刖面：从状态类型分，并不表示一题只从属于一类。其实一类只是一种状态的表示方法。可以好几 种方法组合成一个状态，来解决问题。1.1. 编号(长度)动态规划共性总结本类的状态是基础的基础，大部分的动态规划都要用到它，成为一个维。一般来说，有两种编号的状态：状态(i)表示前i个元素决策组成的一个状态。状态(i)表示用到了第i个元素，和其他在1至U i-1间的元素，决策组成有的一个状态。 题库a) 最长不下降子序列以一元组(i)作为状态，表示第i个作为序列的最后一个点的时候的最长序列。于是 很容易想到O(n2)得算法。但本题可合理组织状态，引入一个单调的辅
2、助数组，利用单 调性二分查找，优化到O(nlogn)。关于优化详见优化章。一些问题可将数据有序化，转化成本题。应用：拦截导弹(NOIP99 Advance 1)就是原题。Beautiful People (sgu199)，要将数据有序化：其中一个权作为第一关键字不下降排 歹L另一个权作为第二关键字不上升。Segment (ural 1078)，将线段的左端点有序化就可以了。b) LCS状态(i,j)，表示第1个字符串的第i位，与第2个字符串的第j位匹配，得到的最长 的串。若有多个串要LCS，则加维，即几个串就几个维。我也将此题归入路径问题。c) 花店橱窗布置(IOI99)见路径问题。1.2.
3、区间动态规划共性总结本类问题与下一章的划分问题的决策的分割点无序交集比较大(占本类问题的30%)。题库a)石子合并见划分问题b) 模版匹配(CEOI01,Patten)这题特殊的地方是状态的值是一个集合而不是一个数。c) 不可分解的编码(ACM World Final 2002)d) Electric Path(ural1143)e) 邮局(IO I2000 Day2 1)若状态表示的思路从第i个村庄可以从属于哪个邮局，无最优子结构。转变一个方 向：第k个邮局可以“控制”一个区间的村庄i,j。于是方程就显然了：f(k,i,j)=minf(k-1,p,i-1)+w(i,j)(k-1=p=i-1)
4、S(i)为村庄i到原点的距离。w(i,j)=mink| 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)=minf(i-1,p-1)+w(p,j)(i-1=p=j-1e(i,j
5、)为当f(i,j)到达最优值时的p.通过证明四边形不等式，得到e(i,j)=e(i,j+1)=e(i+1,j+1)决策数量又少了一个数量级。1.3. 坐标动态规划共性总结之后的一些问题，状态是由坐标维与其他的维组成。本类与划分问题(是2维或多维的 坐标系的划分)与路径问题的交集占本类问题中大多数。题库a) 棋盘分割(NOI99 4)主要是将公式变形，变形后的公式很容易看出方程。状态是由2个坐标组成的4元组(x1,y1)(x2,y2)，表示一个子棋盘。这有点像之前的 区间动态规划，只不过是将1维转2维。后见路径问题。1.4. 数轴动态规划共性总结题库a) 01背包应用：装箱问题(NOIP01 T
6、rade 4)就是原题。值币分割可利用方程的性质，空间降1维。币值可重复的值币分割(pku1742, Problem F LouTianChengs Contest in POJ)使用左右法在定位上加速。另给状态加一个属性last,记录上一次剩下的可用的同币值硬币数(利用了当前 转移是唯一前驱的特点)。b) 取火柴问题(sgu153 Playing with matches)c) Stone Pile(ural1005 Stone Pile)d) 公路巡逻(CTSC2000)1.5.5.树型动态规划共性总结1) 动态规划的顺序一般按照后序遍历的顺序，即处理完儿子再处理当前节点，才符合树的子结构
7、的性 质。2) 多叉树转换为二叉树由于要分配附加维到各个节点，而分配附加维是个划分问题，若还是按当前节点到 各个儿子节点分配，则成了一个整数划分问题,O(n2)。所以要把多叉树转换为二叉树， 这样才能按动态规划的方式只决策当前点的分配问题,O(n)。3) 加当前点的选或不选的常数维加此维解决的是后效性问题。4) 在将边信息转成树时的技巧将读入的边分裂成2条边，将这2条边关联起来(就是找到一条边，另一条边的编 号就知道)。用前向星表示法表示边(按起点有序)，以后用边的时候，用了一条边打不 可用标志，也将关联边打不可用标志。这样可以保证O(n)的时间完成信息处理，而且 在父节点找儿子的过程中带来很
8、大的方便。5) 复杂度树型动态规划复杂度基本上是O(n)；若有附加维m，则是O(nm)。题库a) 选课(CTSC97-3)由于要分配课程数，所以要多叉树转换为二叉树。b) 贪吃的九头龙(NOI02-3)若小头数大于1的话，则让不同的小头吃一段树枝的2个端点。这样就把问题转化成：附加维是大头吃的个数，当前点由不由大头吃的常数维 的动态规划。由于涉及划分问题，所以要多叉树转换为二叉树。c) 求树的质心(sgu134 Centroid)给出一棵边不带权的树，求点，使得去掉此点后,剩下的最大的连通子图的顶点数最 小.d) 求树中的点最远距离最近。给出一棵边带权的树，求树中的点，使得此点到树中的其他结点
9、的最远距离最近。Computer Network (sgu149)Computer Net (ural1056)1.6.集合动态规划（状态压缩）共性总结1）数据特殊性给出的数据在某一个或几个维度上一般具有比较小的范围（可以枚举一类的状态）。一个枚举的状态是一个集合。2）编码由于集合中元素个数的不定性或范围大，直接开数组存，不好索引数组（编程复杂 度太高），所以要将集合编码。利用数据的可枚举性，将枚举的状态（集合）编码。一般来说码值的范围要很小（尽 量排除无用的码值，如炮兵：当前格和上格存在炮兵的情况是非法的，可以排除）。规定编码的码值代表的意思，要尽量规定好维护的码值。（如炮兵：当前格存在炮
10、兵的用2,上格存在炮兵用1。这样下一层的规划时，只要码值-1即可）。有时候可以直接利用编码的顺序动态规划，因为这时编码已经是拓补有序。如TSP 问题当前已选点集合的状态的前驱的编码的值一定比当前的编码的值小。3）状态压缩对有限阶段的放置情况，行走情况编码（其实质也是放置的集合或行走路线的集 合），这样的编码，也有人谓之：“状态压缩”。此类题以“炮兵阵地”为典型，进行扩 展。题库a）购物（IOI95-2）可将每种物品按5进制编码。（5为每种物品数的上限）由于物品数的上限为5，比较小，也可直接开数组存。b）Roger 游戏任务一（CTSC98 Day2 4）一个正方体在一个方格内的状态只有24种，
11、而且可以通过顶面和前面来表示，这 样用3维的状态（x,y,p可以解决，p为1到24种状态中的一种。c）TSP问题观察一下TSP的搜索过程：for （x in未选点）TSP（x）即当前路的最后一个节点为x,现在要选择下一个节点y,W y要在未选点的集合中。 若未选点或已选点的集合已确定，则后效性消除。可以DP。状态为令X为当前路的已 选点的集合（含i），当前路的最后一个节点为i。2元组（X,i）为经过已选点的集合X到节 点i的最短长度。将X编码即可。注意：并没有因为动态规划将问题从NP类带到P类应用：DNA Laboratory（Problem B,TU-Darmstadt Programmin
12、g Contest 2004）将每个串的交迭部分求出，就可以将问题专成TSP但要输出字典序最小的，则需要注意DP顺序。有具体的报告。d）炮兵阵地十分经典，详见报告应用：Another Chocolate Maniac（sgu132）类似炮兵的做法的最值，只不过是求最小 值，麻烦点。Hardwood floor（sgu131）类似炮兵的做法的统计Little Knights(sgu225)类似炮兵的做法的统计,数据量太大要constLittle Kings(sgu223)类似炮兵的做法的统计Bugs公司(CEOI 2002)类似炮兵的做法的最值1.7. 利用动态规划思想求最值，编号(循环变量)的
13、迭代共性总结要利用上次的一些运算“剩下”的循环变量作当前循环的边界，主要在于找出一种决策 顺序，使之成立。题库a) 奶牛浴场b) Communication System将数据有序化，从大到小枚举带宽，每次可利用上次处理的结果Min,来决策当前状态。称作迭代，或就是一种动态规划。(zju1409, Problem C Tehran 2002 Iran Nationwide Internet Programming Contest)1.8. 记忆化搜索题库a) Magic Trick (Problem G, TU-Darmstadt Programming Contest 2004)2. 按转移
14、方式分2.1. 存在性递推1) 01 统计(CTSC99 1)2) 卡特兰数circle(sgu130)3) 鹰蛋2.2. 求一系列的分割(合并)点(划分问题)2.2.1.决策的分割点有序共性总结a)有序性每次决策的点的编号是有序的，即要按决策的顺序输出分割点的编号的话，编号是 有序的，满足分割点的编号按升序排列。b)方程一般形式f(n,m)=optimizef(k,m-1)+w(k+1,n)(n,m)表示从1到n个点中划分为m个部分的最优值；k为决策的分割点，即第m 个部分为k+1至U n； 这里optimize可以为 max,min。题库a) 整数划分常应用在将一个权分配给一定的小分割块，
15、如：将大堆的石子分成一定的小堆，小 堆可为空，大堆要分完。有时应用在树型动态规划(二叉转多叉)中。b) 乘积最大(NOIP00 Advance 2)就是按上面的一般式的方程做。2.2.2. 决策的分割点无序共性总结a) 无序性每次决策的点的编号是无序的，即要按决策的递归顺序输出分割点的编号的话，编号是 无序的。b) 方程一般形式f(i,j)=optimizef(i,k-1)+f(k+1,j)+w(i,j)(i,j)表示从i到j的范围内选取一个分割点k的最优值，子问题是分割点左边(i,k-1)和右 边(k+1,j)的点的范围的最优值；这里optimize可以为max,min。方程很类似2叉树的性质。c) 四边形不等式此类的问题，有些可用四边形不等式优化。见优化章。题库a) 石子合并(NOI95 2)经典，详见报告。可用四边形不等式优化成O(n2)其实还可以用类似堆的数据结构在O(nlogn)的时间内完成，但这就不是动态规划了。应
