树状动态规划.doc

(完整版)树状动态规划

竞 赛
数据结构
数学分析
动态程序设计
搜索
网络流
累计
全国奥林匹克信息学竞赛
分区联赛
2
3
3

8
全国奥林匹克信息学竞赛
2
1
2
1

6
国际奥林匹克信息学竞赛
中国组队赛
1
2
1
1
1`
6
国际奥林匹克信息学竞赛
4
1

1

6
累 计
9
7
6
3
1
26

一、几个知识点回顾
（一）动态规划
1、动态程序设计的定义:
动态程序设计是一个“多阶段最优化决策的过程”。即由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列,同时确定了完成整个过程的一条最优的活动路线(图1。1).

图1.1
2、动态程序设计的几个名词:
⑴状态（State)：表示事物的性质,是描述“动态规划”中的“单元"的量。亦是每一阶段求解过程的出发点。
⑵阶段（Stage）:阶段是一些性质相近,可以同时处理的状态集合,或者说,阶段只是标识那些处理方法相同、处理顺序无关的状态。通常，一个问题可以由处理的先后次序划分为几个阶段.一个阶段既可以包含多个状态，也可以只包含一个状态。阶段与状态的关系很类似分子与原子的关系
阶段的顺序是确定的，不可以调换任两个阶段的顺序
阶段i中某状态的取值仅与阶段i-1中与之相关的所有状态有关，且只对阶段i+1中与之相关的状态取值产生影响
⑶决策（Decision):每个阶段做出的某种选择性的行动，是程序所需要完成的选择。
⑷状态转移方程：是前一个阶段的状态转移到后一个的状态的演变规律，是关于两个相邻阶段状态变化的方程，是“动态规划"的中心.设
fk(i）—k阶段状态i的最优权值，即初始状态至状态i的最优代价
由上可见，所谓最优化决策是指在k—1阶段的所有状态中，究竟选择哪个状态j可使得fk(i)成立.总体上来说，一个“动态规划"算法应该包含上面提到的几种基本关系与属性。由于动态程序设计是按照阶段的顺序，直接在子问题最优解的基础上计算的，“不做已经做过的工作"，因此其效率比搜索法好得多。只要问题的计算过程呈阶段性，且可找到状态转移方程，我们宁可摒弃传统的搜索而采用动态程序设计方法。
（二)哈希表（Hash Table）
根据关健码值直接访问。把关键码映射到表中的一个位置来访问记录的过程.这个映射函数叫做哈希函数,在存放记录的表叫做哈希表。也就是说，将所有元素存储在一张表中,每一个元素具有一个哈希函数，按照如下两种方式给同一个哈希函数值的所有元素分配多个空间(图1。2）：

图1.2
这样，可以经过较少的次数得到所查的元素，提高查询的时间效率。考虑哈希函数的因素有：
计算哈希函数所需时间；
关键字的长度；
哈希表的大小;
关键字的分布情况；
记录的查找频率;
（三）、最大排序二叉树(二叉搜索树、二叉检索树、二分检索树）
是指它要么是一棵空树，要么它的左子树的所有结点比根结点小,右子树的所有结点比树根结点大，它的左子树和右子树分别是一棵排序二叉树。
最大排序二叉树是指在所有的排序二叉树中节点最多的一棵树.
（四）四边形不等式
四边形不等式是Donald E. Knuth从最优二叉搜索树的数据结构中提出的.当函数w［i，j］满足时，称w满足四边形不等式.在动态规划中被运用于证明决策的单调性.
（五）平衡二叉树
二叉搜索树可以实现任何一种基本的动态集合操作，但当树的高度时,这些操作性能可能变差，即不能保证在最坏的情况下动态集合操作的时间为O(lg n）.这样情况是因为二叉树可能变得不平衡.用一组规则让二叉树平衡起来，例如，红－黑树确保了没有一条路径会比任何其他路径长到两倍,因而基本上是平衡的.AVL树应用平衡化旋转规则来完成指针结构的修改。
（六）博弈树
、博弈树的定义:
如果将初始状态作为根结点，把从初始状态的每一个可能棋步出发，进行一轮游戏后得到的所有子状态作为根结点的孩子结点；然后从这些新状态出发进行下一轮游戏，得到的又一批子状态作为新状态的孩子结点，…，依次类推，就可以根据游戏规则产生一棵包罗了各种可能状态变化的树，习惯上称为博弈树(图2.6。1)。

图2。6。1
2、博弈树的特征：
1、 奇数层的状态由先行方进行操作，偶数层的状态由后行方进行操作；
2、 从根结点到当前状态的走步序列（路径)表示了双方依次轮流走过的棋步；
3、 叶子是游戏的终止状态（即状态数为0或先前确定了取珠的洞口）.若叶子处在奇数层,后行方赢；若叶子处在偶数层，先行方赢；
4、在对弈中，双方都想赢，都会采取取胜的策略.
3、构造博弈树的基本思想：
我们在博弈树的每个结点上标一个值F ，由这个值来确定操作方最佳的走法。不妨认为,F 越大对先行方越有利,奇数层结点总是挑选使得Ｆ值最大的方案走；而偶数层结点则恰好相反.由于子结点是由父结点推出来的，故父结点的Ｆ值与其所有子结点的Ｆ值有一定的关系。另一方面，游戏愈接近结束愈便于分析，也便于计算Ｆ值.我们可从叶子结点出发，往上倒推每个结点的Ｆ值，直至初始状态的Ｆ值为止。整棵博弈树建立之后，便产生出取胜的策略。
在过去的信息学竞赛中博弈一类的试题未曾出现过，题型新颖。因此许多选手对解决这类问题的方法（博弈树）比较陌生。本题的出现，可谓是一种积极的“导向”。博弈类试题趣味性和益智性强，要求编程者通过了解对方已经走过的棋步和今后可能走的棋步,“知己知彼”，制定出不含任何机遇因素、真正能“百战不殆”的取胜策略。这方面的实例很多，例如西洋跳棋、一字棋、国际象棋、围棋、余一棋……,创造问题情景的空间很大，具有多样性,是算法研究的重点对象。值得探讨的问题也很多，例如面对实际问题,怎样定义各结点的F值;哪些对象可以在构造博弈树前计算;如何裁剪博弈树的多余分支，等等.这就要求我们的知识结构、编程能力和策略创造能够与时俱进，适应这方面的要求.各个顶点的F值是按照后序遍历的顺序由下而上倒推的，并体现了极大极小的过程，这些都是博弈树的构造原则。对于某些试题来说，F函数实质为一个状态转移方程。由于求解过程是沿有向边一步步倒推的，因此具有阶段性。计算当前顶点的F值必须查阅所有后继顶点的F值，如果程序方在子问题上的策略不是最优的话，将直接导致在当前问题的策略上失去最优性，因此具备了最优子结构和重叠子问题的特征，可以用自上而下的动态程序设计方法递归计算顶点的F值.

二、问题研究
例1、邮局(单调性的确定)
［问题描述］
按照递增顺序给出一条直线上坐标互不相同的n个村庄,要求从中选择p个村庄建立邮局，每个村庄使用离它最近的那个邮局，使得所有村庄到各自所使用的邮局的距离总和最小.
试编程计算最小距离和，以及邮局建立方案.
[算法分析]
本题也是一道动态规划问题，详细分析请看文本附件(邮局解题报告）。将n个村庄按坐标递增依次编号为1，2，……，n，各个邮局的坐标为d［1。.n]，状态表示描述为:m[i,j]表示在前j个村庄建立i个邮局的最小距离和。所以，m［p，n]即为问题的解，且状态转移方程和边界条件为：
m[1,j］=w［1，j］
i≤j
其中w［i，j］表示在d[i..j］之间建立一个邮局的最小距离和，可以证明,当仅建立一个邮局时，最优解出现在中位数,即设建立邮局的村庄为k，则，于是，我们有：
，
同时，令s［i,j］=k，记录使用前i-1个邮局的村庄数,便于在算出最小距离和之后构造最优建立方案.
上述算法中w［i,j］可通过O（n）时间的预处理，在O(1）的时间内算出，所以,该算法的状态总数为O(n*p)，每个状态转移的状态数为O（n)，每次状态转移的时间为O（1），该算法总的时间复杂度为O(p*n2)。
［算法优化］
本题的状态转移方程与①式十分相似，因此我们猜想其决策是否也满足单调性,即
s[i—1,j］≤s[i，j］≤s［i，j+1］
首先，我们来证明函数w满足四边形不等式，即：

设，,下面分为两种情形，z≤y或z〉y，下面仅讨论z≤y，z〉y的情况是类似的。
由i≤z≤y≤j有：

接着，我们用数学归纳法证明函数m也满足四边形不等式。对四边形不等式中“长度”l=j’-i进行归纳:
当i=i’或j=j’时，不等式显然成立。由此可知，当l≤1时,函数m满足四边形不等式。
下面分两种情形进行归纳证明：
情形1：i<i’=j<j’，即m[i，j］+m[j,j'] ≤m[i，j’］,
设k=max{p ｜ m[i,j’]=m[i,p-1］+m［p,j’］+w［i，j’] ｝，再分两种情形k≤j或k〉j。下面只讨论k≤j，k>j的情况是类似的。

情形2：i〈i’<j<j’
设 y=max{p ｜ m［i’，j]=m［i’—1,p]+w[p+1,j] ｝
z=max｛p | m[i,j'］=m［i-1，p]+w[p+1，j’］ }
仍需再分两种情形讨论,即z≤y或z>y。
情形2。1，当z≤y<j〈j’时:

情形2。2，当i—1<i’-1≤y<z〈j'时：

最后，我们证明决策s［i，j］满足单调性。
为讨论方便,令mk[i，j］=m［i-1,k]+w[k+1,j]；
我们先来证明s[i—1，j］≤s[i，j],只要证明对于所有i≤k<k’<j且mk’[i-1,j]≤mk[i-1，j］,有：mk’[i,j]≤mk[i，j］。
类似地，我们可以证明一个更强的不等式
mk[i—1,j]—mk’[i-1，j]≤mk［i,j］-mk’[i，j］
也就是： mk[i—1,j]+mk’[i,j］≤mk[i，j]+mk’[i-1，j]
利用递推定义式展开整理的：m［i—2,k］+m［i-1,k’］≤m［i—1，k]+m［i—2，k’］,这就是i-2〈i-1〈k<k’时m的四边形不等式。
我们再来证明s[i,j］≤s[i,j+1］，与上文类似,设k<k’<j，则我们只需证明一个更强的不等式： mk［i，j］-mk’[i,j]≤mk[i，j+1］—mk’［i,j+1]
也就是: mk[i,j］+mk’［i，j+1]≤mk[i，j+1]+mk’[i，j]
利用递推定义式展开整理的：w[k+1,j]+w［k'+1，j+1]≤w［k+1，j+1］+w[k’+1,j]，这就是k+1<k’+1〈j<j+1时w的四边形不等式.
综上所述，该问题的决策s[i，j]具有单调性,于是优化后的状态转移方程为：
m［1,j］=w[1，j］
i≤j
s[i，j］=k
同上文所述,优化后的算法时间复杂度为O（n＊p)。
（程序及优化前后的运行结果比较见附件)
四边形不等式优化的实质是对结果的充分利用。它通过分析状态值之间的特殊关系，推出了最优决策的单调性，从而在计算当前状态时，利用已经计算过的状态所做出的最优决策，减少了当前的决策量。这就启发我们，在应用动态规划解题时，不仅可以实现状态值的充分利用,也可以实现最优决策的充分利用。这实际上是从另一个角度实现了“减少冗余"。
例2　LOSTCITY （用哈希表、检索树优化DP)
［问题描述]
现给出一张单词表、特定的语法规则和一篇文章：
文章和单词表中只含26个小写英文字母a…z。
单词表中的单词只有名词，动词和辅词这三种词性,且相同词性的单词互不相同。单词的长度均不超过20.
语法规则可简述为:名词短语：任意个辅词前缀接上一个名词；动词短语：任意个辅词前缀接上一个动词;句子：以名词短语开头，名词短语与动词短语相间连接而成。
文章的长度不超过1000。且已知文章是由有限个句子组成的,句子只包含有限个单词。
编程将这篇文章划分成最少的句子,在此前提之下,要求划分出的单词数最少。
[算法分析］
这是也是一道动态规划问题.我们分别用v，u，a表示动词，名词和副词，给出的文章用L［1。。M］表示,则状态表示描述为：
F（v,i）：表示L前i个字符划分为以动词结尾(当i〈〉M时,可带任意个辅词后缀）的最优分解方案下划分的句子数与单词数；
F（u,i）：表示L前i个字符划分为以名词结尾（当i〈>M时,可带任意个辅词后缀）的最优分解方案下划分的句子数与单词数。
过去的分解方案仅通过最后一个非辅词的词性影响以后的决策，所以这种状态表示满足无后效性，
状态转移方程为：
F（v,i)=min｛ F（n,j）+（0，1), L(j+1。.i)为动词；
F(v，j)+(0，1）, L(j+1.。i)为辅词,i<>M；｝
F（n，i)=min{ F（n，j）+（1,1）, L(j+1..i）为名词；
F(v,j)+（0,1）， L（j+1。.i)为名词；
F(n,j）+(0,1), L(j+1。.i）为辅词,i<>M；}
边界条件：F(v,0)=(1,0)； F（n，0)=（∞, ∞)；
问题的解为：min｛ F（v，M）， F(u,M） }；
上述算法中，状态总数为O(M），每个状态转移的状态数最多为20，在进行状态转移时，需要查找L[j+1.。i］的词性，根据其词性做出相应的决策，并引用相应的状态。下面就通过不同的方法查找L［j+1。。i]的词性，比较它们的时间复杂度.
［算法实现］
设单词表的规模为N，首先我们对单词表进行预处理，将单词按字典顺序排序并合并具有多重词性的单词。在查找词性时有以下几种方法：
方法1、采用顺序查找法。最坏情况下需要遍历整个单词表，因此最坏情况下的时间复杂度为O（20*N*M)，比较次数最多可达1000＊5k*20=108，当数据量较大时效率较低。
方法2、采用二分查找法。最坏情况下的时间复杂度为O(20*M＊log2N），最多比较次数降为5k*20＊log21000=106,完全可以忍受.
集合查找最为有效的方法要属采用哈希表了。
方法3、采用哈希表查找单词的词性.首先将字符串每四位折叠相加计算关键值k,然后用双重哈希法计算哈希函数值h（k）。采用这种方法，通过O（N）时间的预处理构造哈希表,每次查找只需O(1）的时间，因此，算法的时间复杂度为O(20*M+N)=O（M）。
采用哈希表是进行集合查找的一般方法，对于以字符串为元素的集合还有更为高效的方法，即采用检索树［3］。
方法四、采用检索树查找单词的词性。由于每个状态在进行状态转移时需要查找的所有单词都是分布在同一条从树根到叶子的路径上的,因此，如果选取从树根走一条路径到叶子作为基本操作，则每个状态进行状态转移时的最多20次单词查找只需O(1)的时间，另外，建立检索树需要O(N)的时间，因此,算法总的时间复杂度虽然仍为O(M)，但是由于时间复杂度的常数因子小于方法三，因此实际测试的速度也最快。
从本题的优化过程可以看出：采用正确的数据结构是算法优化的重要原则，在动态规划算法的优化中也同样适用。方法3使用了哈希表这一高效的集合查找数据结构，方法四使用的针对性更强的检索树，使得算法的时间效率得到了提高.
采用检索树查找字符串只要从树根出发走到叶结点即可，需要的时间正比于字符串的长度。如果哈希函数确实是随机的，那么哈希函数的值与字符串中的每一个字母都有关系。所以，计算哈希函数值的时间与检索树执行一次运算的时间大致相当。但计算出哈希函数值后还要处理冲突.因此,一般情况下,在进行字符串查找时，检索树比哈希表省时间。

例3、排序二叉树（状态的存储）
一个边长为n的正三角形可以被划分成若干个小的边长为1的正三角形，称为单位三角形。如图3。4。1，边长为3的正三角形被分成三层共９个小的正三角形，我们把它们从顶到底,从左到右以1―9编号（见图3.4.1(a)）。同理，边长为n的正三角形可以划分成n2个单位三角形。

图3。4。1
四个这样的边长为n的正三角形可以组成一个三棱锥（见图3.4。1(b)）。我们将正三棱锥的三个侧面依顺时针次序(从顶向底视角）编号为A， B， C，底面编号为D。侧面的A, B， C号三角形以三棱锥的顶点为顶，底面的D号三角形以它与A, B三角形的交点为顶。图3。4。1(b）为三棱锥展开后的平面图，每个面上标有圆点的是该面的顶，该图中侧面A，B，C分别向纸内方向折叠即可还原成三棱锥。我们把这A、B、C、D四个面各自划分成n2个单位三角形。
对于任意两个单位三角形，如有一条边相邻，则称它们为相邻的单位三角形，显然，每个单位三角形有三个相邻的单位三角形。现在，把1～4n2分别随机填入四个面总共4n2个单位三角形中。
现在要求你编程求由单位三角形组成的最大排序二叉树。所谓最大排序二叉树,是指在所有由单位三角形组成的排序二叉树中节点最多的一棵树。对于任一单位三角形，可选它三个相邻的单位三角形中任意一个作为父节点,其余两个分别作为左孩子和右孩子。当然，做根节点的单位三角形不需要父节点，而左孩子和右孩子对于二叉树中的任意节点来说并不是都必须的。
输入:
输入文件为tree。in。其中第一行是一个整数n（1≤n≤18），随后4n2行，依次为三棱锥四个面上所填的数字.
输出：
输出文件为tree.out.其中仅包含一个整数，表示最大的排序二叉树所含的节点数目。
输入输出样例：
Tree.in
3
19
33
32
31
29
3
5
4
30
22
25
20
21
12
24
23
34
35
14
13
15
26
18
17
8
16
27
11
10
9
1
28
7
2
6
36
Tree.out
17

输入文件对应图3。4.2：

图3.4。2
输出样例文件对应的最大排序二叉树如图3.4.3所示:

图3。4。3
［算法分析］这也是动态规划问题。当状态选定后,我们面对的问题就是如何存储状态了。从理论上讲，每一个状态都应该存储两个值
l 此状态的最优的权值
l 决策标识值
但实际中,我们面对的“动态规划"问题很多都是状态数目十分庞大，这就要求我们在存储上必须做一定的优化才可以实现这个算法的程序化。主要的优化就是：舍弃一切不必要的存储量.在一些问题中,题目给出了只在某一范围内的关系，所以我们只需存储这一范围内的状态即可.

【例题二十二】取分（博弈树与DP）
SCORE是一个双人棋盘游戏,参赛者把同一个令牌在棋盘上的一个位置移到另一个位置.棋盘上有N个位置，编号有1到N，还有一组箭头的集合.每个箭头从一个位置指向另一个位置。每个位置都归两参赛者中的一位或另一位拥有，我们称之为该位置的拥有者.此外，每个位置都有一个正的值,所有位置的值均不相同。位置1为开始位置.开始时两个参赛者的分数均为0.
游戏玩法如下。我们用C表示开始走子时的当前令牌位置。游戏开始时C为位置1、游戏的进行包括以下操作：
如果C的值大于C的拥有者的当前分数，则C的拥有者的当前分数被C的值取代，否则C的拥有者的分数不变。在上述两中情况下另一位参赛者的分数不变.
之后，C的拥有者有当前令牌位置中选取一个箭头，而箭头的目的地变为新的当前令牌位置.注意一个参赛者有可能做出好几个连续的移动。
当令牌回到开始位置时游戏结束。胜方为游戏结束时得分最高者。
箭头总是按照以下方式安排：
从当前令牌位置必可以找到一个由此出发的箭头.
每个位置P均可以由开始位置到达，也就是说,由开始位置到P由一系列的箭头。
保证游戏可以在有限数目的移动内结束。
写一个能进行游戏并取胜的程序。无论您是否先行，您的程序设计要求在评测时所有局均能取胜.在评测时对手也会采取优化策略，也就是说一旦他有机会便会取胜，而您的程序则会失败。
输入和输出
您的程序由标准输入读进输入信息并向标准输出写出输出信息。您的程序为一号参赛者而对手为二号参赛者.当您的程序开始时，它应当首先由标准输入读入以下的输入信息：
第一行包括一个整数:位置的数目N,1≤N≤1000.位置乃用数字1到N作区分.
以下N行中每行包括N个用来表示箭头信息的整数。如果由一个箭头由位置i指向位置j，则i行第j个数字为1，否则为0。
接下一行包括N个整数(不是1就是2）,顺序表示每个位置的拥有者。如果位置i为一号参赛者（您自己）所拥有，则第i个整数为1，否则第i个整数为2。
再接下来一行也包括N个数值不同的整数，表示每个位置的值。如果第i个整数为j，则位置i的值也为j。对于各位置的数值j，1≤j≤N成立，N个值的每一个都不相同.
之后，游戏由当前令牌位置1开始。您的程序应按如下进行，并且在令牌会到位置1的时候结束。
如果轮到您的程序走，则您的程序应把下一个位置P写到标准输出，1≤P≤N。
如果轮到对手的程序走，则您的程序应由标准输入读进下一个位置P，1≤P≤N。

考虑以下例子,游戏用图3。5.1表示.用圈表示的位置属于一号参赛者所拥有，而用方块表示的位置属于二号参赛者所拥有。每个位置的值均写在方块内或圈内，而位置标号则写在方块或圈的旁边。图3.5。1和表3.5。1描述了游戏的进行过程。

图3.5。1
标准输入
标准输出
解释
4

N
0 1 0 0

位置1发出的箭头信息
0 0 1 1

位置2发出的箭头信息
0 0 0 1

位置3发出的箭头信息
1 0 0 0

位置4发出的箭头信息
1 1 2 2

位置拥有者
1 3 4 2

位置值

2
一号参赛者走子（把位置2写到标准输出）

4
二号参赛者走子（把位置4写到标准输出)
1
1
一号参赛者走到开始位置-游戏结束
表3.5.1
游戏结束后，一号参赛者得3分而二号参赛者得2分，前者胜。
编程指示
在以下例子中,targe是位置的整形变量。
如果您用C++编程并使用iostream，您该使用以下的方法读入标准输入及写到标准输出；
cin〉〉targe；
cout<〈targe〈<endl〈<flush；
如果您用C或C++编程并使用scanf及printf，您该使用以下的方法读入标准输入及写到标准输出：
scanf（“%d”，&targe);
printf（“%d"，&targe)； fflush(stdout)；
如果您用Pascal编程，您该使用以下方法读入标准输入及写到标准输出：
Readln(targe）；
Writeln（targe)；
[算法分析]各个顶点的F值是按照后序遍历的顺序由下而上倒推的，并体现了极大极小的过程，这些都是博弈树的构造原则。对于某些试题来说，F函数实质为一个状态转移方程。由于求解过程是沿有向边一步步倒推的，因此具有阶段性.计算当前顶点的F值必须查阅所有后继顶点的F值，如果程序方在子问题上的策略不是最优的话，将直接导致在当前问题的策略上失去最优性，因此具备了最优子结构和重叠子问题的特征，可以用自上而下的动态程序设计方法递归计算顶点的F值。

【例题十二】方程的解数（全国赛）
问题描述
已知一个n元高次方程:

其中：x1， x2， …,xn是未知数，k1，k2，…，kn是系数，p1,p2，…pn是指数。且方程中的所有数均为整数。
假设未知数1≤ xi ≤M， i=1，，,n，求这个方程的整数解的个数.

输入文件（equation。in）
文件的第1行包含一个整数n。第2行包含一个整数M.第3行到第n+2行，每行包含两个整数，分别表示ki和pi。两个整数之间用一个空格隔开。第3行的数据对应i=1，第n+2行的数据对应i=n。

输出文件(equation。out）
文件仅一行，包含一个整数,表示方程的整数解的个数。

输入输出样例：
输入
3
150
1 2
-1 2
1 2
输出
178

约束条件
1£n£6；1£M£150；

方程的整数解的个数小于231.
本题中，指数Pi（i=1，2，……，n）均为正整数.