算法涉及度始终不够啊啊,一个个攻进~~DP 始终不够

Dp状态设计与方程总结

1.不完全状态记录
<1>青蛙过河问题
<2>利用区间dp

2.背包类问题
<1> 0-1背包,经典问题
<2>无限背包,经典问题
<3>判定性背包问题
<4>带附属关系的背包问题
<5> + -1背包问题
<6>双背包求最优值
<7>构造三角形问题
<8>带上下界限制的背包问题(012背包)

3.线性的动态规划问题
<1>积木游戏问题
<2>决斗(判定性问题)
<3>圆的最大多边形问题
<4>统计单词个数问题
<5>棋盘分割
<6>日程安排问题
<7>最小逼近问题(求出两数之比最接近某数/两数之和等于某数等等)
<8>方块消除游戏(某区间可以连续消去求最大效益)
<9>资源分配问题
<10>数字三角形问题
<11>漂亮的打印
<12>邮局问题与构造答案
<13>最高积木问题
<14>两段连续和最大
<15>2次幂和问题
<16>N个数的最大M段子段和
<17>交叉最大数问题

4.判定性问题的dp(如判定整除、判定可达性等)
<1>模K问题的dp
<2>特殊的模K问题,求最大(最小)模K的数
<3>变换数问题

5.单调性优化的动态规划
<1>1-SUM问题
<2>2-SUM问题
<3>序列划分问题(单调队列优化)

6.剖分问题(多边形剖分/石子合并/圆的剖分/乘积最大)
<1>凸多边形的三角剖分问题
<2>乘积最大问题
<3>多边形游戏(多边形边上是操作符,顶点有权值)
<4>石子合并(N^3/N^2/NLogN各种优化)

7.贪心的动态规划
<1>最优装载问题
<2>部分背包问题
<3>乘船问题
<4>贪心策略
<5>双机调度问题Johnson算法

8.状态dp
<1>牛仔射击问题(博弈类)
<2>哈密顿路径的状态dp
<3>两支点天平平衡问题
<4>一个有向图的最接近二部图

9.树型dp
<1>完美服务器问题(每个节点有3种状态)
<2>小胖守皇宫问题
<3>网络收费问题
<4>树中漫游问题
<5>树上的博弈
<6>树的最大独立集问题<7>树的最大平衡值问题<8>构造树的最小环
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

1.按状态类型分
写在前面:

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

1.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)

见路径问题。

1.2. 区间动态规划
共性总结

本类问题与下一章的划分问题的决策的分割点无序交集比较大(占本类问题的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)

决策数量又少了一个数量级。

1.3. 坐标动态规划
共性总结

之后的一些问题,状态是由坐标维与其他的维组成。本类与划分问题(是2维或多维的坐标系的划分)与路径问题的交集占本类问题中大多数。

题库

a)棋盘分割(NOI99 4)

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

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

后见路径问题。

1.4. 数轴动态规划
共性总结


题库

a)01背包

应用:

装箱问题(NOIP01 Trade 4)

就是原题。

值币分割

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

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

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

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

b)取火柴问题(sgu153 Playing with matches)

c)Stone Pile(ural1005 Stone Pile)

d)公路巡逻(CTSC2000)

1.5. 5.树型动态规划
共性总结

1) 动态规划的顺序

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

2) 多叉树转换为二叉树

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

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

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

……………………

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

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

5) 复杂度

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

题库

a)选课(CTSC97-3)

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

b)贪吃的九头龙(NOI02-3)

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

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

c)求树的质心(sgu134 Centroid)

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

d)求树中的点最远距离最近。

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

Computer Network (sgu149)

Computer Net (ural1056)

1.6. 集合动态规划(状态压缩)
共性总结

1)数据特殊性

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

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

2)编码

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

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

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

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

3)状态压缩

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

题库

a)购物(IOI95-2)

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

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

b)Roger游戏任务一(CTSC98 Day2 4)

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

c)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 Contest2004)

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

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

有具体的报告。

d)炮兵阵地

十分经典,详见报告。

应用:

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

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

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

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

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

1.7. 利用动态规划思想求最值,编号(循环变量)的迭代
共性总结

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

题库

a)奶牛浴场

b)Communication System

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

(zju1409, Problem C Tehran 2002 Iran Nationwide InternetProgramming Contest)

1.8. 记忆化搜索
题库

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


2. 按转移方式分
2.1. 存在性
递推

1)01统计(CTSC99 1)

2)卡特兰数

circle(sgu130)

3)鹰蛋

2.2. 求一系列的分割(合并)点(划分问题)
2.2.1.决策的分割点有序
共性总结

a)有序性

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

b)方程一般形式

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。

题库

a)整数划分

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

b)乘积最大(NOIP00 Advance 2)

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


2.2.2.决策的分割点无序
共性总结

a)无序性

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

b)方程一般形式

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叉树的性质。

c)四边形不等式

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

题库

a)石子合并(NOI95 2)

经典,详见报告。

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

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

应用:

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


b)多边形(IOI98)

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

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

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

d)括号序列(Problem B, NEERC 2001)

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

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

2.3. 路径问题
共性总结

a)行走方向决定阶段性

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

b)多源或多汇

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

c)双向动态规划

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

d)决策稀疏性

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

e)状态稀疏性

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

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

题库

a)方格取数(NOIP00 advance 4)

(x1,y1)(x2,y2)

对角线空间优化

b)花店橱窗布置(IOI99)

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


3. 动态规划的优化
3.1. 迭代
3.2. 四边形
3.3. 凸性的优化

最主要的未总结,给出相关的题与已有的报告(自己或他人的)

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------


初期:
一.基本算法:
(1)枚举.(poj1753,poj2965)
(2)贪心(poj1328,poj2109,poj2586)
(3)递归和分治法.
(4)递推.
(5)构造法.(poj3295)
(6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996)
二.图算法:
(1)图的深度优先遍历和广度优先遍历.
(2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra)
(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)
(3)最小生成树算法(prim,kruskal)
(poj1789,poj2485,poj1258,poj3026)
(4)拓扑排序(poj1094)
(5)二分图的最大匹配 (匈牙利算法)(poj3041,poj3020)
(6)最大流的增广路算法(KM算法).(poj1459,poj3436)
三.数据结构.
(1)串(poj1035,poj3080,poj1936)
(2)排序(快排、归并排(与逆序数有关)、堆排)(poj2388,poj2299)
(3)简单并查集的应用.
(4)哈希表和二分查找等高效查找法(数的Hash,串的Hash)
(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)
(5)哈夫曼树(poj3253)
(6)堆
(7)trie树(静态建树、动态建树)(poj2513)
四.简单搜索
(1)深度优先搜索(poj2488,poj3083,poj3009,poj1321,poj2251)
(2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)
(3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)
五.动态规划
(1)背包问题.(poj1837,poj1276)
(2)型如下表的简单DP(可参考lrj的书page149):
1.E[j]=opt{D+w(i,j)}(poj3267,poj1836,poj1260,poj2533)
2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij}(最长公共子序列)
(poj3176,poj1080,poj1159)
3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题)
六.数学
(1)组合数学:
算法涉及度始终不够啊啊,一个个攻进~~【DP】 始终不够
1.加法原理和乘法原理.
2.排列组合.
3.递推关系.
(POJ3252,poj1850,poj1019,poj1942)
(2)数论.
1.素数与整除问题
2.进制位.
3.同余模运算.
(poj2635,poj3292,poj1845,poj2115)
(3)计算方法.
1.二分法求解单调函数相关知识.(poj3273,poj3258,poj1905,poj3122)
七.计算几何学.
(1)几何公式.
(2)叉积和点积的运用(如线段相交的判定,点到线段的距离等).(poj2031,poj1039)
(3)多边型的简单算法(求面积)和相关判定(点在多边型内,多边型是否相交)
(poj1408,poj1584)
(4)凸包.(poj2187,poj1113)


中级:
一.基本算法:
(1)C++的标准模版库的应用.(poj3096,poj3007)
(2)较为复杂的模拟题的训练(poj3393,poj1472,poj3371,poj1027,poj2706)
二.图算法:
(1)差分约束系统的建立和求解.(poj1201,poj2983)
(2)最小费用最大流(poj2516,poj2516,poj2195)
(3)双连通分量(poj2942)
(4)强连通分支及其缩点.(poj2186)
(5)图的割边和割点(poj3352)
(6)最小割模型、网络流规约(poj3308,)
三.数据结构.
(1)线段树.(poj2528,poj2828,poj2777,poj2886,poj2750)
(2)静态二叉检索树.(poj2482,poj2352)
(3)树状树组(poj1195,poj3321)
(4)RMQ.(poj3264,poj3368)
(5)并查集的高级应用.(poj1703,2492)
(6)KMP算法.(poj1961,poj2406)
四.搜索
(1)最优化剪枝和可行性剪枝
(2)搜索的技巧和优化(poj3411,poj1724)
(3)记忆化搜索(poj3373,poj1691)

五.动态规划
(1)较为复杂的动态规划(如动态规划解特别的施行商问题等)
(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)
(2)记录状态的动态规划.(POJ3254,poj2411,poj1185)
(3)树型动态规划(poj2057,poj1947,poj2486,poj3140)
六.数学
(1)组合数学:
1.容斥原理.
2.抽屉原理.
3.置换群与Polya定理(poj1286,poj2409,poj3270,poj1026).
4.递推关系和母函数.

(2)数学.
1.高斯消元法(poj2947,poj1487,poj2065,poj1166,poj1222)
2.概率问题.(poj3071,poj3440)
3.GCD、扩展的欧几里德(中国剩余定理)(poj3101)
(3)计算方法.
1.0/1分数规划. (poj2976)
2.三分法求解单峰(单谷)的极值.
3.矩阵法(poj3150,poj3422,poj3070)
4.迭代逼近(poj3301)
(4)随机化算法(poj3318,poj2454)
(5)杂题.
(poj1870,poj3296,poj3286,poj1095)
七.计算几何学.
(1)坐标离散化.
(2)扫描线算法(例如求矩形的面积和周长并,常和线段树或堆一起使用).
(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)
(3)多边形的内核(半平面交)(poj3130,poj3335)
(4)几何工具的综合应用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)


高级:
一.基本算法要求:
(1)代码快速写成,精简但不失风格
(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)
(2)保证正确性和高效性. poj3434
二.图算法:
(1)度限制最小生成树和第K最短路. (poj1639)
(2)最短路,最小生成树,二分图,最大流问题的相关理论(主要是模型建立和求解)
(poj3155,poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446
(3)最优比率生成树. (poj2728)
(4)最小树形图(poj3164)
(5)次小生成树.
(6)无向图、有向图的最小环
三.数据结构.
(1)trie图的建立和应用. (poj2778)
(2)LCA和RMQ问题(LCA(最近公共祖先问题) 有离线算法(并查集+dfs) 和在线算法
(RMQ+dfs)).(poj1330)
(3)双端队列和它的应用(维护一个单调的队列,常常在动态规划中起到优化状态转移的
目的).(poj2823)
(4)左偏树(可合并堆).
(5)后缀树(非常有用的数据结构,也是赛区考题的热点).
(poj3415,poj3294)
四.搜索
(1)较麻烦的搜索题目训练(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)
(2)广搜的状态优化:利用M进制数存储状态、转化为串用hash表判重、按位压缩存储状态、双向广搜、A*算法.(poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)
(3)深搜的优化:尽量用位运算、一定要加剪枝、函数参数尽可能少、层数不易过大、可以考虑双向搜索或者是轮换搜索、IDA*算法.(poj3131,poj2870,poj2286)
五.动态规划
(1)需要用数据结构优化的动态规划.
(poj2754,poj3378,poj3017)
(2)四边形不等式理论.
(3)较难的状态DP(poj3133)
六.数学
(1)组合数学.
1.MoBius反演(poj2888,poj2154)
2.偏序关系理论.
(2)博奕论.
1.极大极小过程(poj3317,poj1085)
2.Nim问题.
七.计算几何学.
(1)半平面求交(poj3384,poj2540)
(2)可视图的建立(poj2966)
(3)点集最小圆覆盖.
(4)对踵点(poj2079)
八.综合题.
(poj3109,poj1478,poj1462,poj2729,poj2048,poj3336,poj3315,poj2148,poj1263)

  

爱华网本文地址 » http://www.413yy.cn/a/25101012/112186.html

更多阅读

盎司等于多少克,一盎司黄金等于多少克 1盎司黄金是多少克

盎司等于多少克,一盎司黄金等于多少克——简介盎[àng]司,分:常衡盎司、金衡盎司、药衡盎司。盎司等于多少克,一盎司黄金等于多少克——方法/步骤盎司等于多少克,一盎司黄金等于多少克 1、金衡盎司主要是对金银等贵金属计量。药衡盎司

教你如何刷MIUI 6.0系统,一键刷机通用图文教程 miui一键刷机v5

教你如何刷MIUI 6.0系统,一键刷机通用图文教程——简介如今小米手机越来越受国人欢迎了,其体验符合国人要求,给大家打来不一样的体验,随着时间的推移,miui 6.0如约而至,作为一刷机爱好者,这边给大家带来一个非小米手机刷MIUI 6.0的刷机教程

声明:《算法涉及度始终不够啊啊,一个个攻进~~DP 始终不够》为网友浅秋分享!如侵犯到您的合法权益请联系我们删除