树型动态规划模型
树型动态规划是建立在树结构上的动态规划，所以阶段很明显，一般是通过孩子结点的最优值推出父亲结点的最优值。一般以结点及相关信息为状态，动态转移方程也是根据父亲结点跟孩子结点之间关系来建立的。通过根的子结点传递有用的信息给根，然后根得出最优解的过程。下面结合一些例子，来介绍它的一般解法。
例1【问题描述】
给你一棵树T=(V,E,W)，其中V表示顶点集且|V|=n,E表示边集。如果
属于E，则W表示的长度。
求两点v，u，使得它们之间的路径总长度最长。你只需要输出这个最长长度即可。
输入格式
输入第1行为n和边数e
接下来e行，每行三个数v，u，和w
输出格式
最长长度
输入样例
6 5
1 2 20
1 3 40
1 4 50
2 5 10
3 6 10
输出样例
100
题目解析
认真审题，其实此题是要在带权树上求最长链，一棵有根树的最长链，可能出现如下图的两种情况:
设dep (i)表示以结点i为根的子树的最大深度。
F(i)表示以结点i为根的子树中包含结点i的最长链长度。
我们有
dep (i) =max{dep (j) +w (i,j)}，其中j是i的子结点
F (i) =max {dep (i), dep (j) +w (i,j) +dep(k)+w(i,k)}，其中j，k是i的子结点，且j<>k
不难发现，我们的状态转移方程是按照从下至上的顺序计算的。
做一遍DFS遍历，在回朔的时候分别计算dep和F的值。
关于F值的计算:由于结点j和k之间没有关联，所以我们只需要选择两个(dep (j)+w(i,j))最大的子结点进行累加即可。
参考程序
const maxn=100;
var n,v,ans:integer;
w: array [0.. maxn, 0.. maxn] of integer;
dep:array [1..maxn] of integer;
used:array [1.. maxn] of boolean;
procedure init;
var i,j,x,y:integer;
begin
assign (input,'line.in');
reset (input);
readln (n,v);
for i:=0 to n do
for j:=0 to n do w[i,j]:=-1;
for i:=1 to v do begin
readln (x,y,w[x, y]);
w[y,x]:=w[x, y];
end;
Fillchar(used, sizeof(used),true);
used [1]:=false;
ans:=0;
close (input);
end;
procedure dfs(x:integer);//求dep和f的过程
var i, max1, max2: integer;
begin
dep [x]:=0; max1:=0; max2:=0;
for i:=1 to n do
if (w [x, i] <>-1)and (used [i]) then begin
used [i] :=False;
dfs (i);
if dep[i] +w[x,i] >=dep[x]then begin
dep[x] :=dep [i]+w[x, i] ;
max2:=max1;
max1:=dep[x];
end
else
if dep[i]+w[x, i] >max2 then max2:=dep [i] +w [x, i];
end;
if dep [x]>ans then ans:=dep[x];
if max1+max2>ans then ans:=max1+max2;
end;
begin
init;
dfs (1);
writeln (ans);
end.
例2.ural 1018二叉苹果树
问题描述
有一棵苹果树，如果树枝有分叉，一定是分2叉(就是说没有只有1个儿子的结点)这棵树共有N个结点(叶子点或者树枝分又点)，编号为卜N，树根编号一定是1。 我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一棵有4个树枝的树
现在这树枝条太多了，需要剪枝。但是一些树枝上长有苹果。
给定需要保留的树枝数量，求出最多能留住多少苹果。
输入格式
第1行2个数，N和Q(1?O?N(lj then j:=k;
end;
f:=j;
End;
以上两个例题是非常简单的树型动态规划，树型动态规划在信息学竞赛中也有许多的应用，如NOIP 2003提高组的加分二叉树(ctsc97的选课，NOI 2002贪吃的九头龙。
加分二叉树
【问题描述】
设一个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
5 7 1 2 10
【输出样例】
145
3 1 2 4 5
[分析]很显然，本题适合用动态规划来解。如果用数组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], valu
1,j-1]+value[i,j-2]*value[j,j], vale[i+2,i+2]+value[i,i+1]*value[i+3,j],…,value[j-
ue[j,j]+value[i,j-1]}
题目还要求输出最大加分树的前序遍历序列，因此必须在计算过程中记下从节点i到节点j所组成的最大加分二叉树的根节点，用数组root[i,j]表示
[PASCAL源程序]
{$N+}
program NOIP2003_3_Tree;
const
maxn=30;
var
i,j,n,d:byte;
a:array[1..maxn]of byte;
value:array[1..maxn,1..maxn]of comp;
root:array[1..maxn,1..maxn]of byte;
s,temp:comp;
f1,f2:text;fn1,fn2,fileNo:string;
procedure preorder(p1,p2:byte);{按前序遍历输出最大加分二叉树}
begin
if p2>=p1 then begin
write(f2,root[p1,p2],' ');
preorder(p1,root[p1,p2]-1);
preorder(root[p1,p2]+1,p2);
end;
end;
begin
write('Input fileNo:');readln(fileNo);
fn1:='tree.in'+fileNo;fn2:='tree.ou'+fileNo;
assign(f1,fn1);reset(f1);
assign(f2,fn2);rewrite(f2);
readln(f1,n);
for i:=1 to n do read(f1,a[i]);
close(f1);
fillchar(value,sizeof(value),0);
for i:=1 to n do begin
value[i,i]:=a[i];{计算单个节点构成的二叉树的加分}
root[i,i]:=i;{
记录
混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载
单个节点构成的二叉树的根节点}
end;
for i:=1 to n-1 do begin
value[i,i+1]:=a[i]+a[i+1];{计算相邻两个节点构成的二叉树的最大加分}
root[i,i+1]:=i;{记录相邻两个节点构成的二叉树的根节点;需要说明的是，两个节点构成的二叉树，其根节点可以是其中的任何一个;这里选编号小的为根节点，则编号大的为其右子树;若选编号大的为根节点，则编号小的为其左子树;因此，最后输出的前序遍历结果会有部分不同，但同样是正确的。如果最大加分二叉树的所有节点的度数都是0或2，则最后输出的前序遍历结果是唯一的。}
end;
for d:=2 to n-1 do begin{依次计算间距为d的两个节点构成的二叉树的最大加分}
for i:=1 to n-d do begin
s:=value[i,i]+value[i+1,i+d];{计算以i为根节点，以i+1至i+d间所有节点为右子树的二叉树的最大加分}
root[i,i+d]:=i; {记录根节点i}
for j:=1 to d do begin
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间所有节点为右子树的二叉树的最大加分}
if temp>s then begin{如果此值为最大}
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间所有节点为左子树的二叉树的最大加分}
if temp>s then begin
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.
浙公网安备 33021202002483