树型动态规划的实例分析完美整理.docx
《树型动态规划的实例分析完美整理.docx》由会员分享，可在线阅读，更多相关《树型动态规划的实例分析完美整理.docx（22页珍藏版）》请在冰点文库上搜索。
树型动态规划的实例分析完美整理
树型动态规划的实例分析
中山市华侨中学——李彦亭
一、什么是树型动态规划
顾名思义，树型动态规划就是在“树”的数据结构上的动态规划，平时作的动态规划都是线性的或者是建立在图上的，线性的动态规划有二种方向既向前和向后，相应的线性的动态规划有二种方法既顺推与逆推，而树型动态规划是建立在树上的，所以也相应的有二个方向：
1．根—>叶：
不过这种动态规划在实际的问题中运用的不多，也没有比较明显的例题，所以不在今天讨论的范围之内。
2．叶－>根：
既根的子节点传递有用的信息给根，完后根得出最优解的过程。
这类的习题比较的多，下面就介绍一些这类题目和它们的一般解法。
二、例题与解析
加分二叉树
【问题描述】
设一个n个节点的二叉树tree的中序遍历为（l,2,3,…,n），其中数字1,2,3,…,n为节点编号。
每个节点都有一个分数（均为正整数），记第i个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：
subtree的左子树的加分×subtree的右子树的加分＋subtree的根的分数
若某个子树为空，规定其加分为1，叶子的加分就是叶节点本身的分数。
不考虑它的空子树。
试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。
要求输出；
（1）tree的最高加分
（2）tree的前序遍历
【输入格式】
第1行：
一个整数n（n＜30），为节点个数。
第2行：
n个用空格隔开的整数，为每个节点的分数（分数＜100）。
【输出格式】
第1行：
一个整数，为最高加分（结果不会超过4,000,000,000）。
第2行：
n个用空格隔开的整数，为该树的前序遍历。
【输入样例】
5
571210
【输出样例】
145
31245
[分析]很显然，本题适合用动态规划来解。
如果用数组value[i,j]表示从节点i到节点j所组成的二叉树的最大加分，则动态方程可以表示如下：
value[i,j]=max{value[i,i]+value[i+1,j],value[i+1,i+1]+value[i,i]*value[i+2,j],value[i+2,i+2]+value[i,i+1]*value[i+3,j],…,value[j-1,j-1]+value[i,j-2]*value[j,j],value[j,j]+value[i,j-1]}
题目还要求输出最大加分树的前序遍历序列，因此必须在计算过程中记下从节点i到节点j所组成的最大加分二叉树的根节点，用数组root[i,j]表示
[PASCAL源程序]
{$N+}
programNOIP2003_3_Tree;
const
maxn=30;
var
i,j,n,d:
byte;
a:
array[1..maxn]ofbyte;
value:
array[1..maxn,1..maxn]ofcomp;
root:
array[1..maxn,1..maxn]ofbyte;
s,temp:
comp;
f1,f2:
text;fn1,fn2,fileNo:
string;
procedurepreorder（p1,p2:
byte）;{按前序遍历输出最大加分二叉树}
begin
ifp2>=p1thenbegin
write（f2,root[p1,p2],''）;
preorder（p1,root[p1,p2]-1）;
preorder（root[p1,p2]+1,p2）;
end;
end;
begin
write（'InputfileNo:
'）;readln（fileNo）;
fn1:
='tree.in'+fileNo;fn2:
='tree.ou'+fileNo;
assign（f1,fn1）;reset（f1）;
assign（f2,fn2）;rewrite（f2）;
readln（f1,n）;
fori:
=1tondoread（f1,a[i]）;
close（f1）;
fillchar（value,sizeof（value）,0）;
fori:
=1tondobegin
value[i,i]:
=a[i];{计算单个节点构成的二叉树的加分}
root[i,i]:
=i;{记录单个节点构成的二叉树的根节点}
end;
fori:
=1ton-1dobegin
value[i,i+1]:
=a[i]+a[i+1];{计算相邻两个节点构成的二叉树的最大加分}
root[i,i+1]:
=i;{记录相邻两个节点构成的二叉树的根节点；需要说明的是，两个节点构成的二叉树，其根节点可以是其中的任何一个；这里选编号小的为根节点，则编号大的为其右子树；若选编号大的为根节点，则编号小的为其左子树；因此，最后输出的前序遍历结果会有部分不同，但同样是正确的。
如果最大加分二叉树的所有节点的度数都是0或2，则最后输出的前序遍历结果是唯一的。
}
end;
ford:
=2ton-1dobegin{依次计算间距为d的两个节点构成的二叉树的最大加分}
fori:
=1ton-ddobegin
s:
=value[i,i]+value[i+1,i+d];{计算以i为根节点，以i+1至i+d间所有节点为右子树的二叉树的最大加分}
root[i,i+d]:
=i;{记录根节点i}
forj:
=1toddobegin
temp:
=value[i+j,i+j]+value[i,i+j-1]*value[i+j+1,i+d];{计算以i+j为根节点，以i至i+j-1间所有节点为左子树，以i+j+1至i+d间所有节点为右子树的二叉树的最大加分}
iftemp>sthenbegin{如果此值为最大}
s:
=temp;root[i,i+d]:
=i+j;{记下新的最大值和新的根节点}
end;
end;
temp:
=value[i,i+d-1]+value[i+d,i+d];{计算以i+d为根节点，以i至i+d-1间所有节点为左子树的二叉树的最大加分}
iftemp>sthenbegin
s:
=temp;root[i,i+d]:
=i+d+1;
end;
value[i,i+d]:
=s;
end;
end;
writeln（f2,value[1,n]:
0:
0）;{输出最大加分}
preorder（1,n）;{输出最大加分二叉树的前序遍历序列}
close（f2）;
end.
[点评]基本题。
考查了二叉树的遍历和动态规划算法。
难点在于要记录当前最大加分二叉树的根节点。
疑点是最大加分二叉树的前序遍历序列可能不唯一。
Ps：
其实这题真正意义上来说还是一道普通的dp题目，但它批上了树的外表，所以都拿来作对比和讨论。
Ural1018 二*苹果树
题目
有一棵苹果树，如果树枝有分叉，一定是分2叉（就是说没有只有1个儿子的结点）
这棵树共有N个结点（叶子点或者树枝分叉点），编号为1-N,树根编号一定是1。
我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。
下面是一颗有4个树枝的树
2 5
\/
3 4
\/
1
现在这颗树枝条太多了，需要剪枝。
但是一些树枝上长有苹果。
给定需要保留的树枝数量，求出最多能留住多少苹果。
输入格式
第1行2个数，N和Q（1<=Q<=N,1N表示树的结点数，Q表示要保留的树枝数量。
接下来N-1行描述树枝的信息。
每行3个整数，前两个是它连接的结点的编号。
第3个数是这根树枝上苹果的数量。
每根树枝上的苹果不超过30000个。
输出格式
一个数，最多能留住的苹果的数量。
样例输入
52
131
1410
2320
3520
样例输出
21
解析：
因为题目一给出就是二叉的，所以很容易就可以写出方程：
a（I,j）:
=max（a（i.left,k）+a（i.right,j-k））,0<=k<=j
源程序代码：
由于比较简单便不给完全的代码了。
Functiontreedp（x,y:
longint）:
longint;
VarI,j,k:
longint;
Begin
J:
=0;
ForI:
=0toydo
begin
k:
=treedp（b[x].l,I）+treedp（b[x].r,y-I）;
ifk>jthenj:
=k;
end;
treedp:
=j;
End;
选课
[问题描述]
在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。
现在有N门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程a是课程b的先修课即只有学完了课程a，才能学习课程b）。
一个学生要从这些课程里选择M门课程学习，问他能获得的最大学分是多少？
输入：
第一行有两个整数N,M用空格隔开。
（1<=N<=200,1<=M<=150）
接下来的N行,第I+1行包含两个整数ki和si,ki表示第I门课的直接先修课，si表示第I门课的学分。
若ki=0表示没有直接先修课（1<=ki<=N,1<=si<=20）。
输出：
只有一行，选M门课程的最大得分。
样例：
输入：
74
22
01
04
21
71
76
22
输出：
13
解析：
这题比苹果树多了一个步骤就是把一棵普通树转化为二叉树。
读入数据时把二叉树建好：
第一个孩子作为父节点的左子树，其它孩子作为第一个孩子的右子树。
F（x，y）：
表示节点x取y门课得最高学分，则
F（x，y）＝max（f（x.l,k-1）+x.v+f（x.r,y-k））k=0,1,..y
f（x.l,k-1）+x.v（课程x的学分）:
表示选了课程x,左孩子选k-1门课,共k门课。
f（x.r,y-k）表示右孩子只能选y-k门课。
标程中节点－1表示空节点，0是根节点，1—n是n门可选课程的节点.
思考:
若本题加上选那些课程可得到这个最大学分,怎样修改程序？
实现：
怎么实现，是在竞赛中的很重要的一个问题，如果你想ac了这道题目的话，你应该熟悉怎么把一棵树转化成二叉树，完后怎么用递规的思想来实现动态规划。
所以坚实的基础是很重要的东西，如果没有了基础，什么都是空中楼阁。
程序中已经边读边把二叉树建立好了。
源程序代码：
programbluewater;
type
tree=record
l,r,k:
longint;
end;
var
s:
string;
i,j,k,l:
longint;
n,m:
longint;
a:
array[0..200]oftree;
b:
array[-1..200,0..150]ofinteger;
f:
array[0..200]oflongint;
proceduretreedp（x,y:
longint）;
vari,j,k,l:
longint;
begin
ifb[x,y]>=0thenexit;
treedp（a[x].r,y）;{只有右子树的情况}
j:
=b[a[x].r,y];
fork:
=1toydo{左右子树都有的情况}
begin
treedp（a[x].l,k-1）;
treedp（a[x].r,y-k）;
i:
=b[a[x].l,k-1]+b[a[x].r,y-k]+a[x].k;
ifi>jthenj:
=i;
end;
b[x,y]:
=j;
end;
begin
readln（s）;
assign（input,s）;reset（input）;
readln（n,m）;
fillchar（f,sizeof（f）,0）;
fori:
=0tondo
begina[i].l:
=-1;a[i].r:
=-1;a[i].k:
=-1;end;
{buildtree}
fori:
=1tondo
begin
readln（k,l）;
a[i].k:
=l;
iff[k]=0thena[k].l:
=i
elsea[f[k]].r:
=i;
f[k]:
=i;
end;
{bianjie}
fori:
=-1tondo
forj:
=-1tomdo
if（i=-1）or（j=0）thenb[i,j]:
=0elseb[i,j]:
=-1;
{treedp}
treedp（a[0].l,m）;
{output}
writeln（b[a[0].l,m]）;
end.
Tju1053技能树
Problem
玩过Diablo的人对技能树一定是很熟悉的。
一颗技能树的每个结点都是一项技能，要学会这项技能则需要耗费一定的技能点数。
只有学会了某一项技能以后，才能继续学习它的后继技能。
每项技能又有着不同的级别，级别越高效果越好，而技能的升级也是
需要耗费技能点数的。
有个玩家积攒了一定的技能点数，他想尽可能地利用这些技能点数来达到最好的效果。
因此他给所有的级别都打上了分，他认为
效果越好的分数也越高。
现在他要你帮忙寻找一个分配技能点数的方案，使得分数总和最高。
Input
该题有多组测试数据。
每组测试数据第一行是一个整数n（1<=n<=20）,表示所有不同技能的总数。
接下来依次给出n个不同技能的详细情况。
每个技能描述包括5行。
第一行是该技能的名称。
第2行是该技能在技能树中父技能的名称，名称为None则表示该技能不需要任何的先修技能便能学习。
第3行是一个整数L（1<=L<=20），表示这项技能所能拥有的最高级别。
第4行共有L个整数，其中第I个整数表示从地I-1级升到第I级所需要的技能点数（0级表示没有学习过）。
第5行包括L个整数，其中第I个整数表示从第I-1级升级到第I级的效果评分，分数不超过20。
在技能描述之后，共有两行，第1行是一个整数P，表示目前所拥有的技能点数。
接下来1行是N个整数，依次表示角色当前习得的技能级别，0表示还未学习。
这里不会出现非法情况。
Output
每组测试数据只需输出最佳分配方案所得的分数总和。
SampleInput
3
FreezingArrow
IceArrow
3
333
1546
IceArrow
ColdArrow
2
43
1017
ColdArrow
None
3
332
1552
10
001
SampleOutput
42
Source
浙江省2004组队赛第二试
解析：
这题是选课的加强版，但并难不倒我们
还是把一棵树转换为二叉树，完后从子节点到根节点作一次dp，最后得到最优解
由于和上题很相像就不写方程了。
源代码程序：
programbluewater;
type
tree=record
s,sf:
string;
l,r,m:
longint;
c:
array[1..20]oflongint;
d:
array[1..20]oflongint;
end;
var
i,j,k,l,m,n:
longint;
a:
array[0..20]oftree;
b:
array[0..20]oflongint;
learn:
array[0..20]oflongint;
f:
array[0..20,0..8000]oflongint;
functiontreedp（x,y:
longint）:
longint;
vari,j,k,l,max,o,p,q:
longint;
begin
iff[x,y]<>-1thenbegintreedp:
=f[x,y];exit;end;
max:
=treedp（a[x].r,y）;
{learn>0}
iflearn[x]>0then
begin
fork:
=0toydo
begin
i:
=treedp（a[x].l,k）+treedp（a[x].r,y-k）;
ifi>maxthenmax:
=i;
end;
end;
{learn=0}
l:
=0;p:
=0;i:
=0;
foro:
=1toa[x].mdo
begin
ifo>learn[x]then
beginl:
=l+a[x].c[o];p:
=p+a[x].d[o];end;
fork:
=0toy-ldo
begin
i:
=treedp（a[x].l,k）+treedp（a[x].r,y-l-k）+p;
ifi>maxthenmax:
=i;
end;
end;
f[x,y]:
=max;
treedp:
=max;
end;
functionfind（x:
string）:
longint;
vari,j:
longint;
begin
fori:
=0tondo
ifa[i].s=xthenbreak;
find:
=i;
end;
begin
whilenot（eof（input））do
begin
{input}
readln（n）;
fillchar（a,sizeof（a）,0）;
fillchar（b,sizeof（b）,0）;
a[0].s:
='None';
fori:
=1tondo
witha[i]do
begin
readln（s）;
readln（sf）;
readln（m）;
forj:
=1tomdoread（c[j]）;readln;
forj:
=1tomdoread（d[j]）;readln;
end;
readln（m）;
ifm>8000thenm:
=8000;
fori:
=1tondoread（learn[i]）;readln;
{buildbinarytree}
fori:
=1tondo
begin
k:
=find（a[i].sf）;
ifb[k]=0then
beginb[k]:
=i;a[k].l:
=i;end
elsebegina[b[k]].r:
=i;b[k]:
=i;end;
end;
{bianjie}
fori:
=0to20do
forj:
=0to8000do
f[i,j]:
=-1;
fori:
=0to8000dof[0,i]:
=0;
{main}
writeln（treedp（a[0].l,m））;
end;
end.
战略游戏
Problem
Bob喜欢玩电脑游戏，特别是战略游戏。
但是他经常无法找到快速玩过游戏的办法。
现在他有个问题。
他要建立一个古城堡，城堡中的路形成一棵树。
他要在这棵树的结点上放置最少数目的士兵，使得这些士兵能了望到所有的路。
注意，某个士兵在一个结点上时，与该结点相连的所有边将都可以被了望到。
请你编一程序，给定一树，帮Bob计算出他需要放置最少的士兵.
Input
第一行为一整数Ｍ，表示有Ｍ组测试数据
每组测试数据表示一棵树，描述如下：
第一行N，表示树中结点的数目。
第二行至第N+1行，每行描述每个结点信息，依次为：
该结点标号i，k（后面有k条边与结点I相连）。
接下来k个数，分别是每条边的另一个结点标号r1，r2，...，rk。
对于一个n（0Output
输出文件仅包含一个数，为所求的最少的士兵数目。
例如，对于如下图所示的树：
答案为1（只要一个士兵在结点1上）。
SampleInput
2
4
011
1223
20
30
5
33142
110
20
00
40
SampleOutput
1
2
Source
sgoi
分析：
这题有2种做法，一种是比较简单但不是很严密的贪心，如果测试数据比较刁钻的话就不可能ac，而这题是一道比较典型的树型动态规划的题目，这题不但要考虑子节点对他的根节点的影响，而且每放一个士兵，士兵所在位置既影响他的子节点也影响了他的根节点。
不过状态还是很容易来表示的，动规实现也不是很难，不过这在这些例题中也有了些“创新”了。
而且这题不是一个对二叉树的dp，而是对一颗普通树的dp，所以更具代表性。
源程序代码：
programbluewater;
const
maxn=1500;
var
i,j,k,l:
longint;
m,n,p,q:
longint;
a:
array[0..maxn,0..maxn]ofboolean;
b:
array[0..maxn]oflongint;
c:
array[0..maxn]ofboolean;
functionleaf（x:
longint）:
boolean;
vari,j:
longint;
t:
boolean;
begin
t:
=true;
fori:
=0ton-1do
ifa[x,i]thenbegint:
=false;break;end;
leaf:
=t;
end;
functiontreedp（x:
longint）:
longint;
vari,j,k,l:
longint;
begin
j:
=0;{add}
k:
=0;{leaf}
l:
=0;{notputnotleaf}
fori:
=0ton-1do
if（a[x,i]）and（x<>i）then
ifleaf（i）theninc（k）else
begin
j:
=j+treedp（i）;
ifnot（c[i]）theninc（l）;
end;
{puanduan}
if（k>0）or（l>0）thenbeginc[x]:
=true;treedp:
=j+1;exit;end;
if（j>0）and（l=0）thenbegintreedp:
=j;exit;end;
end;
begin
{input}
readln（m）;
forp:
=1tomdo
begin
fillchar（b,sizeof（b）,0）;
fillchar（a,sizeof（a）,false）;
fillchar（c,sizeof（c）,false）;
readln（n）;
fori:
=1tondo
begin
read（k,l）;
forj:
=1toldo
begin
read（q）;
a[k,q]:
=true;
b[q]:
=1;
end;
readln;
升级会员 