按状态类型分

写在前面：

从状态类型分，并不表示一题只从属于一类。其实一类只是一种状态的表示方法。可以好几种方法组合成一个状态，来解决问题。

编号（长度）动态规划

共性总结

本类的状态是基础的基础，大部分的动态规划都要用到它，成为一个维。

一般来说，有两种编号的状态：

状态(i)表示前i个元素决策组成的一个状态。

状态(i)表示用到了第i个元素，和其他在1到i-1间的元素，决策组成有的一个状态。

题库

1. 最长不下降子序列

以一元组(i)作为状态，表示第i个作为序列的最后一个点的时候的最长序列。于是很容易想到O(n²)得算法。但本题可合理组织状态，引入一个单调的辅助数组，利用单调性二分查找，优化到O(nlogn)。关于优化详见优化章。

一些问题可将数据有序化，转化成本题。

应用：

拦截导弹(NOIP99 Advance 1) 就是原题。

Beautiful People (sgu199)，要将数据有序化：其中一个权作为第一关键字不下降排列，另一个权作为第二关键字不上升。

Segment (ural 1078)，将线段的左端点有序化就可以了。

2. LCS

状态(i,j)，表示第1个字符串的第i位，与第2个字符串的第j位匹配，得到的最长的串。若有多个串要LCS，则加维，即几个串就几个维。我也将此题归入路径问题。

3. 花店橱窗布置(IOI99)  见路径问题。

区间动态规划

共性总结

本类问题与下一章的划分问题的决策的分割点无序交集比较大（占本类问题的30%）。

题库

1. 石子合并

见划分问题

2. 模版匹配(CEOI01,Patten)

这题特殊的地方是状态的值是一个集合而不是一个数。

3. 不可分解的编码(ACM World Final 2002)

4. Electric Path(ural1143)

5. 邮局(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维或多维的坐标系的划分)与路径问题的交集占本类问题中大多数。

题库

1. 棋盘分割(NOI99 4)

主要是将公式变形，变形后的公式很容易看出方程。

状态是由2个坐标组成的4元组(x1,y1)(x2,y2)，表示一个子棋盘。这有点像之前的区间动态规划，只不过是将1维转2维。

后见路径问题。

数轴动态规划

共性总结

题库

1. 01背包

应用：

装箱问题（NOIP01 Trade 4）

就是原题。

值币分割

   可利用方程的性质，空间降1维。

币值可重复的值币分割(pku1742, Problem F LouTianCheng’s Contest in POJ)

使用左右法在定位上加速。

另给状态加一个属性last,记录上一次剩下的可用的同币值硬币数（利用了当前转移是唯一前驱的特点）。

2. 取火柴问题(sgu153 Playing with matches)

3. Stone Pile(ural1005 Stone Pile)

4. 公路巡逻(CTSC2000)

树型动态规划

共性总结

1. 动态规划的顺序

一般按照后序遍历的顺序，即处理完儿子再处理当前节点，才符合树的子结构的性质。

2. 多叉树转换为二叉树

由于要分配附加维到各个节点，而分配附加维是个划分问题，若还是按当前节点到各个儿子节点分配，则成了一个整数划分问题,O(n_­²)。所以要把多叉树转换为二叉树，这样才能按动态规划的方式只决策当前点的分配问题, O(n_­)。

3. 加当前点的选或不选的常数维

           加此维解决的是后效性问题。

4. 在将边信息转成树时的技巧

将读入的边分裂成2条边，将这2条边关联起来（就是找到一条边，另一条边的编号就知道）。用前向星表示法表示边（按起点有序），以后用边的时候，用了一条边打不可用标志，也将关联边打不可用标志。这样可以保证O(n)的时间完成信息处理，而且在父节点找儿子的过程中带来很大的方便。

5. 复杂度

树型动态规划复杂度基本上是O(n)；若有附加维m，则是O(nm)。

题库

1. 选课(CTSC97-3)

由于要分配课程数，所以要多叉树转换为二叉树。

2. 贪吃的九头龙(NOI02-3)

若小头数大于1的话，则让不同的小头吃一段树枝的2个端点。

这样就把问题转化成：附加维是大头吃的个数，当前点由不由大头吃的常数维的动态规划。由于涉及划分问题，所以要多叉树转换为二叉树。

3. 求树的质心(sgu134 Centroid)

给出一棵边不带权的树，求点,使得去掉此点后,剩下的最大的连通子图的顶点数最小.

4. 求树中的点最远距离最近。

给出一棵边带权的树，求树中的点，使得此点到树中的其他结点的最远距离最近。

Computer Network (sgu149)

Computer Net (ural1056)

集合动态规划（状态压缩）

共性总结

1. 数据特殊性

给出的数据在某一个或几个维度上一般具有比较小的范围（可以枚举一类的状态）。

一个枚举的状态是一个集合。

2. 编码

由于集合中元素个数的不定性或范围大，直接开数组存，不好索引数组（编程复杂度太高），所以要将集合编码。

利用数据的可枚举性，将枚举的状态(集合)编码。一般来说码值的范围要很小（尽量排除无用的码值，如炮兵：当前格和上格存在炮兵的情况是非法的，可以排除）。

规定编码的码值代表的意思，要尽量规定好维护的码值。（如炮兵：当前格存在炮兵的用2，上格存在炮兵用1。这样下一层的规划时，只要码值-1即可）。

有时候可以直接利用编码的顺序动态规划，因为这时编码已经是拓补有序。如TSP问题当前已选点集合的状态的前驱的编码的值一定比当前的编码的值小。

3. 状态压缩

对有限阶段的放置情况，行走情况编码（其实质也是放置的集合或行走路线的集合），这样的编码，也有人谓之：“状态压缩”。此类题以“炮兵阵地”为典型，进行扩展。

题库

1. 购物（IOI95-2）

可将每种物品按5进制编码。（5为每种物品数的上限）

由于物品数的上限为5，比较小，也可直接开数组存。

2. Roger游戏任务一（CTSC98 Day2 4）

一个正方体在一个方格内的状态只有24种，而且可以通过顶面和前面来表示，这样用3维的状态(x,y,p)就可以解决，p为1到24种状态中的一种。

3. TSP问题

观察一下TSP的搜索过程： for (x in 未选点) TSP(x)

即当前路的最后一个节点为x,现在要选择下一个节点y,而y要在未选点的集合中。若未选点或已选点的集合已确定，则后效性消除。可以DP。状态为令X为当前路的已选点的集合(含i)，当前路的最后一个节点为i。2元组(X,i)为经过已选点的集合X到节点i的最短长度。将X编码即可。

注意：并没有因为动态规划将问题从NP类带到P类。

应用: DNA Laboratory(Problem B,TU-Darmstadt Programming Contest 2004)

将每个串的交迭部分求出，就可以将问题专成TSP

但要输出字典序最小的，则需要注意DP顺序。

有具体的报告。

4. 炮兵阵地

十分经典，详见报告。

应用:

Another Chocolate Maniac(sgu132) 类似炮兵的做法的最值，只不过是求最小值，麻烦点。

Hardwood floor(sgu131) 类似炮兵的做法的统计

Little Knights(sgu225) 类似炮兵的做法的统计,数据量太大要const

Little Kings(sgu223) 类似炮兵的做法的统计

Bugs公司(CEOI 2002) 类似炮兵的做法的最值

动态规划思想求最值，编号（循环变量）的迭代

共性总结

要利用上次的一些运算“剩下”的循环变量作当前循环的边界，主要在于找出一种决策顺序，使之成立。

题库

1. 奶牛浴场

2. Communication System

将数据有序化, 从大到小枚举带宽, 每次可利用上次处理的结果Min, 来决策当前状态。称作迭代, 或就是一种动态规划。

(zju1409, Problem C Tehran 2002 Iran Nationwide Internet Programming Contest)

记忆化搜索

题库

1. 1. Magic Trick (Problem G, TU-Darmstadt Programming Contest 2004)

按转移方式分

存在性

递推

1)01统计(CTSC99 1)

2)卡特兰数

circle(sgu130)

      3)鹰蛋

求一系列的分割（合并）点（划分问题）

决策的分割点有序

共性总结

1. 有序性

每次决策的点的编号是有序的，即要按决策的顺序输出分割点的编号的话，编号是有序的，满足分割点的编号按升序排列。

2. 方程一般形式

f(n,m)=optimize{f(k,m-1)+w(k+1,n)}

(n,m)表示从1到n个点中划分为m个部分的最优值；k为决策的分割点，即第m个部分为k+1到n；这里optimize可以为max,min。

题库

1. 整数划分

常应用在将一个权分配给一定的小分割块，如：将大堆的石子分成一定的小堆，小堆可为空，大堆要分完。有时应用在树型动态规划（二叉转多叉）中。

2. 乘积最大(NOIP00 Advance 2)

就是按上面的一般式的方程做。

决策的分割点无序

共性总结

1. 无序性

每次决策的点的编号是无序的，即要按决策的递归顺序输出分割点的编号的话，编号是无序的。

2. 方程一般形式

f(i,j)=optimize{f(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叉树的性质。

3. 四边形不等式

此类的问题，有些可用四边形不等式优化。见优化章。

题库

1. 石子合并(NOI95 2)

经典，详见报告。

可用四边形不等式优化成O(n²)

其实还可以用类似堆的数据结构在O(nlogn)的时间内完成，但这就不是动态规划了。

应用：

构造最优二叉排序树(CTSC96 2)

2. 多边形(IOI98)

这题值的正负号处理要注意，乘法运算，由于符号的加入，使原本的正的最优解，一下变成负的。

3. 加分二叉树(NOIP03 Advance 3)

方程就是一般式，转移的函数：w(i,j)=sum(i,k-1)*sum(k+1,j)+d(k)。由于w(i,j)不满足凸单调性，所以不能用四边形不等式优化。

4. 括号序列(Problem B, NEERC 2001)

这题的分割点不是一个元素，而是元素间的一条线。

主要的思维方式是从递归定义。

路径问题

共性总结

1. 行走方向决定阶段性

有规定源点与终点。每次行走方向都有一定的规定，使原点到终点的所有路径形成无环有向图。

2. 多源或多汇

当多源或多汇时，应该加维，使得每个源，都有一个路径的状态与之对应。如有n个源的网格类问题，常常转态是(x1,y1)(x2,y2)…(xn,yn)。但是源太多的话，空间上不允许，可以降问题转成网络流问题。

3. 双向动态规划

由于有规定源点与终点，可以双向动态规划，但要考虑效果好不好，理论上是比原来少1/2，但有时由于可用于决策的状态较少，效果就不错了。

4. 决策稀疏性

就是所谓走法，若对于一个状态，它的前驱或者后继数很少(从无环有向图角度，就是入度或出度少)，称决策稀疏。

5. 状态稀疏性

就是很多状态是没有用的，如排列的LCS,状态为2维的(x,y)，但对于一个x只有一个y是有效个。所以实质上状态数还是线形的。

本类一些技巧性的东西较多，在题库中具体说明。

题库

1. 方格取数(NOIP00 advance 4)

(x1,y1)(x2,y2)

对角线空间优化

2. 花店橱窗布置(IOI99)

我对本题有个小改造：若花瓶无序，如何做，有序指：对于花束i<花束j, 花束i对应的花瓶编号<花束j对应的花瓶编号。那么这样就是一个NP问题了，可用后面的基于状态压缩的动态规划解决。

插头DP

先献上陈丹琦的大作http://www.docin.com/p-46797997.html

只浅浅的研究了最最基础的几个类型:多条回路,一条回路,简单路径
当时局限于括号表示法,死活无法继续研究更深层次的:广义路径
后来厚着脸皮问陈丹琦要了uva Black and White的代码,研读数遍之后”大彻大悟”,脱离了括号表示法,用最小表示法效率同样很高,并且操作非常方便.即便是最最复杂的情况用最小表示法也可以方便的表示

先来补充一下上篇文章介绍的简单的几个插头:

• 多条回路问题
  这类题目属于最简单的类型,其原因是任意插头可以合并:不仅两个原来不连一起的插头能合并,原来连一起的插头合并后就变成一条完整的封闭回路.不必考虑插头的左右情况,只需要用01状态表示有或者没有就可以了
  这类题目比较简单,变化不是很多:

   

  • hdu 1693 Eat the Trees
    这题属于插头的入门,其实这题做了后还不能说学过插头DP了
  • zju 3466 The Hive II
    这题其中心算法和上题一样,不过六边形的处理比四边形的处理难了不止一点点,由于边没有对齐状态会增减,并且横着做会讨论奇偶性,建议竖着做,那样会方便不少
• 一条回路问题
  上文说过多条回路问题简单是因为任意插头可以合并,那么一条回路问题的难点就是已经连在一起的插头不能随意合并(不然的话就不止一条回路了)
  这类题目只是多了左右插头的讨论,cdq的论文里有详细的讲解,这种题算是真正的入门了,所以有好一部分题目可以练习:

   

  • ural 1519 Formula 1
    论文里详细介绍的题,也可以称之为模板题,我在此题刷了N遍
  • poj 1739 Tony’s Tour
    楼教的男人八题之一,根据题意算是简单路径问题,但是确定了起始点和终点,可以变化当成是一条回路问题
    其实不必像论文里一样加一圈外围构造,只要以左插头在起点开始,右插头在终点结束(可以当做我们已经把起末点连起来了),中间还是过程一样
  • hdu 1964 Pipes
    这题不再算方案数,而是算路径的最大权值,DP转移的时候处理一下就好了
  • zju 3256 Tour in the Castle
    M这么大,很明显只有矩阵快速幂才能解决,用插头DP建立出每一列的各个情况的转移,然后扔个矩阵模板
  • hdu 3377 Plan
    和楼教的题一样,是简单路径问题但是由于确定了的起末点,变化可成回路问题,这题较前几题不同之处在于不是每个点都必须要走,这只要在处理两个空插头合并的时候再加一个情况即可
  • fzu 1977 Pandora adventure
    在上题的基础上又加了一些必须要走的点,同样,在必须要走的点上加处理即可
  • World Finals – Harbin – 2009/2010 Channel
    那年finals的压轴题之一,要求找一条最长路,路之间不能有任何的接触(包括角上)
    虽然只有这一个条件,看上去很简单的样子,但是考虑全面后却非常烦
    只要输出一种方案就行,就是说不用dp,只要记录状态的转移就好了,下边我们来简单分析一下:
    首先按楼教那题一样我们先在脑中把起点和终点连起来.
    要求路不能有任何接触,其实只要保证和左上角还有右上角不要有接触就行,因为左边或者上边有接触的话必然存在左上和右上的接触,反过来说,所以只要防止左上角和右上角有接触,也就没有左边和上边的接触,(我表述不给力.绕了一大堆=.=)
    但是按原来的路走会出现和上边,左边,左上,右上的接触啊,怎么判断这两种情况的不同呢?
    我们再在上边的理论反过来理解:只要上边接触,那么可以和左上,右上接触;只要左边接触,那么就可以和左上接触.
    于是我们只要记录轮廓线上方一格是不是有路,然后转移的时候把上述一些非法的情况判掉就OK了
• 简单路径问题
  和上述类型的不同之处在于起点和终点不必重合,所以又衍生出了一个独立插头,这样变化情况就有4*4(空插头,左插头,右插头,独立插头)的讨论了,不如最小表示法来的方便
  我找到的题目很少只有一道:

   

  • zju 3213 Beautiful Meadow
    这题没有什么变化,正好可以拿来练习简单路径
    我会贴出这题括号表示法的模板,删掉独立插头部分的话就可以是一条回路问题的模板了
    (里边我用了一个HashMap,顾名思义其实就是用hash实现map的功能,自己写一个这个的话效率会比map高很多)
• 其他插头问题:
  插头的变化确实非常奇妙,下边举一个例子:

   

  • poj 3133 Manhattan Wiring
    我们来分析这道题目,乍一看好像是两条简单路径
    但我们上边讲过,确定了起点终点的简单路径就可以当成一条回路问题
    再看题意,是求最少的路径把各自的点连起来,那么我们就利用求最小值这一点用多条回路的方法来做(在别的地方多加几条回路也没关系,因为不影响最终答案的最小值)
    于是用三进制就可以搞定,这样优化下来是不是觉得很奇妙?

下面深入研究广义路径:
所谓广义路径就是可以是任意形状的联通路,这样的话你就没办法找到路径和头和尾,会像一棵树一样扩充出很多枝叶,状态比前几个类型多了很多,陈丹琦在论文里很巧妙的在括号表示法的基础上加了一个中间插头表示衍生出去的枝叶,但是这样就有5个插头:空插头,左插头,右插头,独立插头,中间插头.讨论的话就有5*5的情况,每种情况又有很多延伸出去的状态,而且只能用if else来搞,出错的概率之高 构思复杂度之大可想而知(而我也只在最最普通的广义路径题目里Topcoder srm312 Div1 1000用过括号表示法,人肉了两个5*5的表>_<,当时写那个程序证明了括号表示法确实能搞广义路径题目,同时也为我纠结了大半年的思想误区作了祭奠)

多么美妙的插头dp啊,哈利路亚!

• 这类题目由于可以变化任意形状的关系,可以延伸出各式各样的题,并且都是难题!
  但是用神奇的最小表示法来表达状态的话可以很方便的完整状态的转移,这为之后除了插头以外更多的限制条件(也就是多了好几维状态)提供了便利.
  下边重点讲一些题目:

   

  • Topcoder srm312 Div1 CheapestIsland
    模板题,我会在下边分别提供括号表示和最小表示的代码(最小表示的代码可以算是这类题目的基础模板,括号表示就挂出来纪念一下,呵呵)

     

  • NOI 2007day2 生成树计数(可以下载题目和数据)
    一道看是和插头无关的题论文里提供一个很奇妙的思路转化成了广义路径问题
    同时给我们提供了新的思路把插头问题进行了进一步的扩展:连通性只和前N项有关的连通性问题都可以用上述方法解决.
    举一反三例如哈密顿回路计数之类的题目自然也能解决了.
  • uva10572 black&white
    hdu 3633 Black and white
    下边这题是我在做完uva那题后改编的,在格子上加了权值,需要多记录了一维状态
    贴一下我写的解题报告好了:

     

    如果看过cdq那篇《基于连通性状态压缩的动态规划问题》的话,可以很容易发现这是一道状态压缩DP问题,很明显的强调了连通性.
    此题改编自Uva10532(Black & White)在原题的基础上增加的格子上的数字,要保证数字差值最小且输出总方案数,所以要在原来的基础上增加一维表示差值.
    具体解法如下:
    对于每个轮廓线,记录的是上方m个格子的连通性(用最小表示法记录,广义路径的用插头表示法的话讨论的状态太多)上方m个格子的颜色和左上角的颜色(用m+1位的二进制就能准确表示,其实记录左边第一个方格的颜色就能推出剩下m-1个方格的颜色,根据"相连格子不是一个连通块的话颜色不相同,是的话相同"这个显而易见的结论,这样子状态精简了很多,只用2位的二进制表示,但是状态数并没有减少,转移的系数反而增加了--要计算颜色,所以并不必要这么做),以及|sumBlack - sumWhite|.
    由于最小表示法没办法精确存储,所以要用散列hash,或者直接map.
    转移的时候,每个格子有一到两个填色方案
    以黑色为例转移如下:
    If 最后一格 && 左白 && 上白 && 左上黑	Then 照成不连通,非法
    If 左黑 && 上黑 && 左上黑 		Then 形成2x2的格子,非法
    If 上白 && 轮廓线上没有和上边相连的格子
    	If 轮廓线上有白色的格子		Then 照成不连通, 非法
    	If 当前格不是最后两格		Then 非法
    	   (因为如果剩下格子有白色,照成不连通 剩下格子全黑色,必然有2x2的黑色格子)
    If 左黑 && 上黑			Then 合并两个连通块
    Else If 左白 && 上白		Then 形成新的连通块
    Else If 左黑 && 上白		Then 和左边的合并
    Else If 左白 && 上黑		Then 和上边的合并
    最后对所有状态判断一下最多只能存在两个连通块
    至于输出一个方案的话只要每次记录这个状态是从哪转来的,另外开两个数组记录前驱和当前颜色就好了.
    
    在极限情况下(8*8的矩阵全是'.',数字随机)测了200组,最大的状态有180W,单个格子最大的状态7W.
    

  • uva10531 Maze Statistics
    很神奇的题意,n*m的地图每个格子都有一定概率会制造出障碍,问你起点和终点连通的状况下每个点有障碍出现的概率是多少?
    一开始看这题,概率论没学好的人(比如说我)一定晕乎乎的,但是,只要你觉得这题目好玩(又比如说我),那就一定能攻克!
    首先我们看看一开始能求出点什么:起点到终点有通路的概率(dp转移的时候概率拿来乘就好).
    根据这个我们可以求出:设一个点存在障碍的时候有通路的概率为x,不存在障碍的时候有通路的概率为y
    那么该点最终存在的概率就是x/(x+y)
    这样只要做n*m*2次插头dp就能解出了
    P.S.这题一定还有更简单的解法或者优化方法,我这做n*m*2次插头dp的方法实在是太次了
  • zju 2125 Rocket Mania 
    zju 2126 Rocket Mania Plus
    论文上有详细解说并且有很多针对性的优化
    P.S.这题真难写,要针对-+LT进行四次分类讨论,写很长的状态转移,深思熟虑之后还是写了近300行…
  • spoj cake3 Delicious Cake 
    这题大赞,非常好的题.一眼看上去好像是和传统意义上的广义路径不同,由于联通块之内不能有切痕,是个完完全全的联通块,原来的话连通块内还能有不同的插头线路,这题完全将这类连线形成的相同连通块全部归为了一类.
    这题难点在于:当两个连通块合并的时候,会发现之前已经有切痕将他们隔开,或者一个连通块转移出去的时候,会在中间产生切痕,虽然路径不同,但是在这题的条件下是相同的.
    为了防止这类情况的发生,我们可以再加一维来表示第i个和第j个连通块之间已经产生过切痕,以后就不要合并他们,产生新状态的时候也要防止和已经连通的块之间产生切痕.
    由于n和m最小值的最大值为5,所以用5*5的01进制表就能表达(其实只需要用到4*5/2=10位就够了),完美解决
  •  

优化技术

• 全局相关文章
• 相关文章