状态表示状态转移(进阶篇).doc

动态规划总结专题一 状态表示在用动态规划解题时，我么往往第一个考虑的是数组维数，其实数组维度（和状态表示）是有规律可循的：A. 二维空间的DP：一般采用二位数组di，j表示当i，j为某一边角时的极值（e：di，j可以表示以i，j为右上角时所能构成的正方形的边长最大值听不懂？接着往下看）。 还有一种表示方法：di，num表示走到第i各阶段的第num个位置：1 2 3 4 5 61234561，12，23，34，45，56，62，13，24，35，46，57，53，14，25，36，47，48，44，15，26，37，38，39，35，16，27，28，29，210，26，17，18，19，110，111，1这种表示解决“多次访问同一图”类的DP题很有用。B. 阶段决策类的DP：这里指阶段划分十分明显的题（0/1背包）。一般采用di,j表示执行到第i各阶段，剩余代价为j时，所能取得的最高分。（如果限制条件多，可增加维度）。C. 树形关系类的DP：一般用di来表示以i为根节点的最优值，可以加维来保证正确性。D. 线性关系类的DP：这一类的DP最简单，是每一个OIER的必备基础，在这里就不废话了。专题二 状态转移（专题二与专题一的分类标准不同，因为dugushuiyi说这样分更好，感谢他）A. 线性转移一般公式：di= operation（dj+wj，i）（wi为由j转移到i的消耗）operation为求最值B. 阶段性转移一般公式：di，j：= operation（di-1，k+wk，j，di-2，） 如果只涉及到前面的有限个阶段，可以使用滚动数组。DI mod n，j= operation（d(i-1)mod n，k+wk，j，d(i-2)mod n，）C. 树性转移一般公式：Di，j=max（dlsoni，k1+wj，k1，drsoni，k2+wj，k2）遍历顺序一般为后序遍历顺序。D. 多维空间转移一般公式：di，j:=max(di-1,j+w1,di,j-1+w2)复杂度分析：DP的复杂度为:状态表示的数组维数*状态转移的代价So A 的复杂度为O（n2） BCD:O(n3);专题三 题目分类总结一、 一般类试题题库：最长不下降子序列最长匹配前缀邮票组合共性总结：1、 题目一般可以通过for 语句来枚举状态，所以时间复杂度为O（N2）本类的状态是基础的基础，大部分的动态规划都要用到它，成为一个维。一般来说，有两种编号的状态：状态(i)表示前i个元素决策组成的一个状态。状态(i)表示用到了第i个元素，和其他在1到i-1间的元素，决策组成有的一个状态。二、 01背包：（重点）题库：01背包（USACO、vijos1025、1104）装箱问题（NOIP01 Trade 4）、取火柴问题(sgu153 Playing with matches)共性总结：1、 一般都从阶段的角度来表示状态2、 因为di，j只与di-1，k有关，所以可以用滚动数组来实现。Dodd（i），j各例分析：1、 采药（NOIP2006、vijos） 一个背包，每个物品只能放一次。 (1)Di，j：=max（di，j，di，j-ti+pi）；DI,j表示决策了前i个物品，花费了j的代价优化：滚动数组.(2)Dodd（i），j：=max（di-1，j，dodd（i-1），j-ti+pi）；观察(2)不难发现，当我们算到j时，1j-1并没有更新，而di-1，j-ti一定在1j-1的范围内，所以完全可以用一位数组，方程为：di：=max（di，di-tj+pj）在最外层循环一下j就ok了。（精益求精）2、 总分（USACO） 一个背包，可以重复放物品。 Di：=max（di，di-tj+pj） Di表示花费i各单位时间所能达到的最大值。（较简单）3、 Raucous Rockers（USACO） 多个背包，不可以重复放物品，但放物品的顺序有限制。dI,j,k:=max(dI-1,j,k,dI-1,j,k-ti+pi,di-1,j-1,maxtime-ti) dI,j,k表示决策到第i个物品、第j个背包，此背包花费了k的空间。dI-1,j,k表示不取i，dI-1,j,k-ti表示取了i病房入背包j中，di-1,j-1,maxtime-ti 表示取了i病房入背包j-1中。比较好理解。（本题也可以用滚动数组优化）4、 Fence Rails（USACO）多个背包，不可以重复放物品，但放物品的顺序无限制。这道题只能用search做了，因为放物品的顺序无限制，无论怎么表示状态，都不能保证无后效性。（为什么1 、2题可以？想一想。因为只有一个背包）背包为题的版本还有很多，但万变不离其宗，我们应该抛开背景，来观察问题的实质。我也做过和1、2、3类似的背包问题，有些版本和1、2、3极像，但不能使用DP，因为它将一些本质的条件更改了。三、 旅游DP：题库：方格取数(NOIP00 advance 4)旅行商简化版（VIJOS）（欧几里德回路）巡游加拿大（IOI95、USACO）三取方格数（VIJOS）Hill（VIJOS）花店橱窗布置(IOI99)共性分析：1、行走方向决定阶段性有规定源点与终点。每次行走方向都有一定的规定，使原点到终点的所有路径形成无环有向图。2、决策稀疏性就是所谓走法，若对于一个状态，它的前驱或者后继数很少(从无环有向图角度，就是入度或出度少)，称决策稀疏。3、状态稀疏性就是很多状态是没有用的，如排列的LCS,状态为2维的(x,y)，但对于一个x只有一个y是有效个。所以实质上状态数还是线形的。4 、 阶段划分不明显（1、2、3 by Amber）各例分析：1、 一取方格数m*n的方格内填上一些数，从1，1出发，只能向上或向右走， 走到m，n使得所经方格的数字之和最大。 题目很简单，不说了。2、 三取方格数与上题类似，要求走三遍（可以重复），使得三遍所经方格的数字之和最大。1 2 3 4 5 6本题的状态表示用到了开始时的表格（一个人走三次=三个人走一次）1234561，12，23，34，45，56，62，13，24，35，46，57，53，14，25，36，47，48，44，15，26，37，38，39，35，16，27，28，29，210，26，17，18，19，110，111，1dnum,i,j,k:=max(dnum-1,i-1,j,k, dnum-1,i-1,j-1,kdnum-1,i-1,j-1,k-1, dnum-1,i-1,j,k-1dnum-1,i,j,k, dnum-1,i-1,j-1,kdnum-1,i,j-1,k-1, dnum-1,i-1,j,k-1)dnum，i，j，k表示三个人在第num各阶段，的i，j，k位置（i=jj。分析状态(i,j)，它可能是(k,j)(jki)中k到达i得到（方式1），也可能是(j,k)(kj)中k超过j到达i得到（方式2）。但它不能是(i,k)(kj)中k到达j得到，因为这样可能会出现重复路径。即使不会出现重复路径，那么它由(j,k)通过方式2同样可以得到，所以不会遗漏解。所以状态转移方程是：di,j=maxdk,j+1(k,i可达且jki),dj,k+1(k,i可达且kj)。时间复杂度O(n3)（by forverstar）四、 环形DP：题库：数字游戏（VIJOS）HILL（VIJOS）看似很难，只要想清楚就可以了。五、 树形DP：题库：加分二叉树（NOI、VIJOS）选课（NOI、VIJOS）这两道题网上的解题报告很多，我就不罗嗦了。其他练习题：a) 括号序列(Problem B, NEERC 20