[学科竞赛]树型动态规划

树型动态规划补充二叉树的遍历的相关知识：在二叉树的应用中，常常要求在树中查找具有某种特征的结点，或者对全部结点逐一进行某种处理。这就是二叉树的遍历问题。所谓二叉树的遍历是指按一定的规律和次序访问树中的各个结点，而且每个结点仅被访问一次。“访问”的含义很广，可以是对结点作各种处理，如输出结点的信息等。遍历一般按照从左到右的顺序，共有3 种遍历方法，先（根）序遍历，中（根）序遍历，后（根）序遍历。先序遍历的操作定义如下：若二叉树为空，则空操作，否则 访问根结点 先序遍历左子树 先序遍历右子树先序遍历右图结果为：124753689中序遍历的操作定义如下：若二叉树为空，则空操作，否则 中序遍历左子树 访问根结点 中序遍历右子树中序遍历右图结果为：742513869后序遍历的操作定义如下：若二叉树为空，则空操作，否则 后序遍历左子树 后序遍历右子树 访问根结点后序遍历右图结果为：745289631满二叉树：一棵深度为h且有 2h-1个结点的二叉树。满二叉树一定为完全二叉树，但是完全二叉树不一定为满二叉树。若设二叉树的深度为h，除第 h 层外，其它各层 (1h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。满二叉树有如下性质：如果一颗树深度为h，最大层数为k，且深度与最大层数相同，即k=h;1、它的叶子数是： 2(h-1)2、第k层的结点数是： 2(k-1)3、总结点数是： 2k-1 (2的k次方减一)4、总节点数一定是奇数。完全二叉树：若设二叉树的深度为h，除第 h 层外，其它各层 (1h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。1、 求pascal中二叉树的前序遍历给你一棵二叉树 Input 输入第一行为该树中结点的个数n，第二行到第n1行分别为这n个结点的值（也代表序号），左子树和右子树，Output 输出二叉树的中序遍历Sample Input 51 2 32 4 53 0 04 0 05 0 0Sample Output 42513参考程序：const max=100;var a:array1.max,1.3 of longint; i,j,n:longint; s:set of 1.max;procedure tree(k:longint); begin if ak,20 then tree(ak,2); writeln(ak,1); if ak,30 then tree(ak,3); end;begin readln(n); s:=1.n; for i:=1 to n do begin readln(ai,1,ai,2,ai,3); s:=s-ai,2,ai,3; end; for i:=1 to n do if i in s then break; tree(i);end.2、愚蠢的矿工(RQNOJ30)题目：背景Stupid 家族得知在HYC家的后花园里的中央花坛处,向北走3步,向西走3步,再向北走3步,向东走3步,再向北走6步,向东走3步,向南走12步,再向西走2步( - -|)就能找到宝藏的入口,而且宝藏都是藏在山里的,必须挖出来,于是Stupid家族派狗狗带领矿工队去挖宝藏.(HYC家的宝藏被狗狗挖走后有什么感想?)描述这个宝藏的制造者为了掩盖世人耳目,他做的宝藏是没有出口,只有入口,不少建造宝藏的人都死在里面.现在知道宝藏总共有N个分岔口,在分岔口处是有财宝的,每个宝藏点都有一个财富值.狗狗只带了M个人来,而且为了安全起见,在每个分岔口,必须至少留一个人下来,这个留下来的人可以挖宝藏(每个人只能挖一个地方的宝藏),这样才能保证不会迷路,而且这个迷宫有个特点,任意两点间有且只有一条路可通（这一句是关键，由此我们可以判断用二叉树来做）.狗狗为了让他的00开心,决定要尽可能地多挖些宝藏回去.现在狗狗的圈叉电脑不在身旁,只能求救于你了,你要知道,狗狗的终身幸福就在你手上了.（狗狗ps：00，你不能就这样抛弃偶）输入/输出格式：输入第1行：两个正整数N,M .N表示宝藏点的个数,M表示狗狗带去的人数(那是一条懒狗,他自己可不做事)。(n=1000,m=100)第2行：N个整数,第i个整数表示第i个宝藏的财富值.(保证|wi|maxint)第N+2行：两个非负整数A和B，表示A通向B,当A=0,表示A是入口.（保证A,B=0 then exit; dp(treex.r,y); fx,y:=ftreex.r,y; for p:=1 to y do begin dp(treex.r,y-p); dp(treex.l,p-1); tmp:=ftreex.r,y-p+ftreex.l,p-1+treex.k; if fx,ytmp then fx,y:=tmp; end; end;begin readln(n,m); for i:=-1 to n do begin treei.l:=-1; treei.r:=-1; end; for i:=1 to n do read(treei.k); for i:=1 to n do begin readln(j,k); if vj=0 then treej.l:=k else treevj.r:=k; vj:=k; end; for i:=-1 to n do for j:=-1 to m do if (j=0)or(i=-1) then fi,j:=0 else fi,j:=-1; dp(tree0.l,m); writeln(ftree0.l,m);end.参考程序2:type node=record x,y,c:longint;【这一次我居然奇迹般地用了type.】end;var z:array0.1002 of node;【这个z.x,z.y,z.c分别代表左节点，右节点，和中间那个（貌似叫父节点）】 n,m:longint; ps:array0.1002 of longint; f:array0.1001,0.100 of longint;【fi,j代表最后到第i个洞用j人的最大宝藏数】 ss:array0.1002 of longint;【ss是用来判断一个洞里与哪个洞相连】 x,y:longint; i,j:longint;procedure dp(x,y:longint);【同志们这个真的是dp啊，没骗你们.】var i,max:longint;begin if fx,y-1 then exit;【不解释.】 dp(zx.y,y);【从右节点做】 max:=fzx.y,y;【max是用来记录最大值的】 for i:=1 to y do begin dp(zx.x,i-1); dp(zx.y,y-i); if (max=3)种商品C1，C2，C3，Cn，其中Ci和Ci+1是不能同时购买的（i=1,2,n-1），而且C1和Cn也不能同时购买。请编程计算可以接生的最大金额数。输入格式第一行两个整数K，M（1=K=1000），其中K表示超低价商品数，K种商品的编号依次为1，2，3，K；M表示不能同时购买的商品对数。接下来K行，第i行有一个整数Xi表示购买编号为i的商品可以节省的金额（1=Xi=100）。再接下来M行，每行两个数A，B，表示A和B不能同时购买，1=A,Bb then exit(a)else exit(b);end;procedure make(x:longint); var i:longint; begin vx:=true; for i:=1 to px,0 do if not vpx,i then begin tx,0:=tx,0+1; tx,tx,0:=px,i; make(px,i); end; end;procedure work(x:longint); var i:longint; begin if tx,0=0 then begin f1,x:=0; f2,x:=cx; exit; end; for i:=1 to tx,0 do work(tx,i); for i:=1 to tx,0 do begin f1,x:=f1,x+max(f1,tx,i,f2,tx,i); f2,x:=f2,x+f1,tx,i; end; f2,x:=f2,x+cx; end;Beginreadln(n,m);for i:=1 to n do readln(ci);for i:=1 to m do begin readln(a,b); pa,0:=pa,0+1;pa,pa,0:=b; pb,0:=pb,0+1;pb,pb,0:=a; end;for i:=1 to n do if pi,0=0 then s:=s+ci else if not vi then begin make(i); work(i); s:=s+max(f1,i,f2,i); end;writeln(s);End.4、 没有上司的舞会【问题描述】 有个公司要举行一场晚会。为了让到会的每个人不受他的直接上司约束而能玩得开心，公司领导决定：如果邀请了某个人，那么一定不会再邀请他的直接的上司，但该人的上司的上司，上司的上司的上司都可以邀请。已知每个人最多有唯一的一个上司。 已知公司的每个人参加晚会都能为晚会增添一些气氛，求一个邀请方案，使气氛值的和最大。 【输入：】 第1行一个整数N（1=N=6000）表示公司的人数。 接下来N行每行一个整数。第i行的书表示第i个人的气氛值x（-128=xb then max:=a else max:=b; end;procedure dfs(v:word); begin while nowv0 do begin dfs(childnowv); inc(yesv,nochildnowv); inc(nov,max(yeschildnowv,nochildnowv); nowv:=prenowv; end; end;begin read(n); for i:=1 to n do read(yesi); fillchar(pres,sizeof(pres),1); root:=n*(n+1) div 2; for i:=1 to n-1 do begin read(x,y); childi:=x; prei:=nowy; nowy:=i; if presx then begin dec(root,x); presx:=false; end; end; dfs(root); writeln(max(yesroot,noroot);end.5、 选课【问题描述】 学校实行学分制。每门的必修课都有固定的学分，同时还必须获得相应的选修课程学分。学校开设了 N （N300）门的选修课程，每个学生可选课程的数量M 是给定的。学生选修了这 M 门课并考核通过就能获得相 应的学分。 在选修课程中，有些课程可以直接选修，有些课程需要一定的基础知识，必须在选了其它的一些课程的基础上才能选修。例如FrontPage必须在选修了Windows 操作基础之后才能选修。我们称Windows 操作基础是FrontPage的先修课。每门课的直接先修课最多只有一门。两门课也可能存在相同的先修课。 每门课都有一个课号，依次为 1，2，3，。 例如: 表中 1是 2的先修课，2是 3、4的先修课。如果要选3，那么 1和 2都一定已被选修过。 你的任务是为自己确定一个选课方案，使得你能得到的学分最多，并且必须满足先修课优先的原则。假定课 程之间不存在时间上的冲突。 【输入格式】 输入文件的第一行包括两个整数N、M （中间用一个空格隔开）其中1N300,1MN。 以下N行每行代表一门课。课号依次为 1，2，N。每行有两个数（用一个空格隔开），第一个数为这门课先修课的课号（若不存在先修课则该项为 0），第二个数为这门课的学分。学分是不超过10的正整数。 【输出格式】 输出文件只有一个数：实际所选课程的学分总数。 【输入样例】 7 4 2 2 0 1 0 4 2 1 7 1 7 6 2 2 【输出样例】 13解法一：分析：首先可以从题目中看出这是一类树形动态规划题。为了方便储存，可以将多叉树转化为二叉树，常用的表示方法是左孩子右兄弟表示法。设fi,j表示以i为节点选j门课所获得的最大学分，则fI,J:=max(flefti,k+frighti,j-k);0=ky then exit(x);exit(y);end;procedure treedp(k,l:longint);var i:longint;begin if (l=0)or(k=0) then exit; if fk,l0 then exit; treedp(rightk,l); fk,l:=frightk,l; for i:=0 to l-1 do begin treedp(leftk,i); treedp(rightk,l-i-1); fk,l:=max(fk,l,fleftk,i+frightk,l-i-1+costk); end;end;begin init; fillchar(f,sizeof(f),0); treedp(root,m); writeln(froot,m);end.解法二：const filename=score;type xx=record left,right,num:longint; end;var f:array0.300,0.300 of longint; son:array0.300 of longint; tree:array0.300 of xx; n,m:longint;function dfs(v,p:longint):longint;var i,t,max:longint;begin if fv,p=0 then exit(fv,p); /若该值已求出，或者改位置为哨兵位置则跳出 if (v=0) or (p=0) then begin fv,p:=0; exit(0); end; max:=dfs(treev.right,p); for i:=0 to p-1 do /在进入“部分选择来自此节点的儿子节点，部分选择来自此节点和平行的兄弟节点”状态 begin t:=dfs(treev.left,i)+dfs(treev.right,p-i-1)+treev.num; if tmax then max:=t; end; fv,p:=max; exit(fv,p);end; procedure init;var i,x:longint;begin readln(n,m); fillchar(son,sizeof(son),0); fillchar(f,sizeof(f),$8F); for i:=1 to n do /左孩子右兄弟表示法 begin readln(x,treei.num); if sonx=0 then treex.left:=i else treesonx.right:=i; sonx:=i; end;end; begin assign(input,filename+.in); reset(input); assign(output,filename+.out); rewrite(output); init; writeln(dfs(tree0.left,m); close(input); close(output);end.解法三：【问题分析】事先说明题目描述有个漏洞，应该是二个以上的课程可能有同一个先修课。换句话讲，一个课程可能是多个课程的先修课，可是一个课最多只有一个先修课。这样的描述好象和我们以前学过的一种数据结构的描述一样。你想对了，就是树。因为是建立在树这种数据结构上的最优化问题，我们自然想到了树型动态规划。想到树型动态规划，那么第一步就是想这课树是否是二叉树，如果不是，是否需要转化呢？显然这个问题不是二叉树，有应为问题是在多个课程中选M个，也就是说是树中一棵或多棵子树的最优解，这样问题就需要转化成二叉树了。注意题目中说一个课程没有先修课是0，也就是说这课树的根是0。把数据结构确定了以后就要想动态规划的三要素了。树型动态规划阶段的具有共性：树的层数，状态是结点，但是只描述结点显然不够，需要在加一个参数。于是我们想到设计一个状态opti,j表示以i为跟的树，选j个课程可获得的最优解。因为树是以0为根的而0又必须要选所以问题的解不是opt0,m而是opt0,m+1。决策是什么呢？对于二叉树我在设计决策时习惯分类讨论这样结构清晰。这棵树只有左子树：要选左子树中的课程，那么根结点一定要选，所以决策就是在左子树中选j-1个课程，在加上选根结点可获得的分数。这棵树只有右子树： 因为右子树和根在原问题中是兄弟关系，所以选右子树中的课程未必要选根，这样决策就有两条：（1）在右子树中选j个的最优值。（2）在右子树中选j-1个的最优值加上选根结点可获得的分数。都有： 这种情况的决策很容易想到，从左子树中选k-1个，从右子树中选j-k个的最优值加上根结点可获得的分数。 但要注意，当K=1也就是左子树选0个时，根结点可以不选，右子树可以选j个而不是j-1个；当然根结点也可以选，选了根结点右子树就得选j-1个了。针对不同情况写出状态转移方程：max(optti.L,j-1+ti.data) （只有左子树）opti,j = max(optti.r,j-1+ti.data, optti.r,j) （只有右子树） max(optti.L,k-1+optti.r,j-k+ti.data,optti.r,j)（都有） (1=ky then max:=x; end;function TreeDp(i,j:longint):longint; var k:longint; begin if opti,j0 then begin if (Ti.L0) and (Ti.r0) then begin if j1 then opti,j:=0 else opti,j:=Ti.data; end else if (Ti.L=0) and (Ti.r0) then opti,j:=max(opti,j,TreeDp(Ti.L,j-1)+Ti.data) else if (Ti.L=0) then begin opti,j:=max(opti,j,TreeDp(Ti.r,j); opti,j:=max(opti,j,TreeDp(Ti.r,j-1)+Ti.data); end else begin opti,j:=max(opti,j,TreeDp(Ti.r,j); for k:=1 to j do opti,j:=max(opti,j,TreeDp(Ti.L,k-1)+TreeDp(Ti.r,j-k)+Ti.data); end; end; TreeDp:=opti,j; end;begin init; writeln(TreeDp(0,m+1);end.解法四：program xuanke;type arr=record left,right:longint; end;var x,t,y,n,m,i:longint; tree:array0.1001of arr; f:array0.1001,0.1001of longint; a:array0.1001of longint;function max(a,b:longint):longint;begin if ab then exit(a); exit(b);end;function find(x,y:longint):longint;var ans,i:longint;begin if x=-1 then exit(0); if fx,y-1 then exit(fx,y); if y=0 then exit(0); ans:=find(treex.right,y); for i:=0 to y-1 do begin ans:=max(ans,find(treex.left,i)+find(treex.right,y-1-i)+ax); end; fx,y:=ans; exit(ans);end;procedure main;begin readln(n,m); fillchar(tree,sizeof(tree),$ff); a0:=0; for i:=1 to n do begin readln(x,y); ai:=y; if treex.left=-1 then treex.left:=i else begin t:=treex.left; while treet.right-1 do t:=treet.right; treet.right:=i; end; end; fillchar(f,sizeof(f),$ff); writeln(find(0,m+1);end;begin main;end.6、 河流（TYVJ1506）几乎整个Byteland 王国都被森林和河流所覆盖。小点的河汇聚到一起，形成了稍大点的河。就这样，所有的河水都汇聚并流进了一条大河，最后这条大河流进了大海。这条大河的入海口处有一个村庄Bytetown。 在Byteland国，有n个伐木的村庄，这些村庄都座落在河边。目前在Bytetown，有一个巨大的伐木场，它处理着全国砍下的所有木料。木料被砍下后，顺着河流而被运到Bytetown的伐木场。Byteland 的国王决定，为了减少运输木料的费用，再额外地建造k个伐木场。这k个伐木场将被建在其他村庄里。这些伐木场建造后，木料就不用都被送到Bytetown了，它们可以在 运输过程中第一个碰到的新伐木场被处理。显然，如果伐木场座落的那个村子就不用再付运送木料的费用了。它们可以直接被本村的伐木场处理。 注：所有的河流都不会分叉，形成一棵树，根结点是Bytetown。 国王的大臣计算出了每个村子每年要产多少木料，你的任务是决定在哪些村子建设伐木场能获得最小的运费。其中运费的计算方法为：每一吨木料每千米1分钱。 编一个程序： 1从文件读入村子的个数，另外要建设的伐木场的数目，每年每个村子产的木料的块数以及河流的描述。 2计算最小的运费并输出。 【输入格式】第一行包括两个数n（2=n=100），k（1=k=50,且k=n）。n为村庄数，k为要建的伐木场的数目。除了Bytetown 外，每个村子依次被命名为 1，2，3n，Bytetown被命名为0。 接下来n行，每行3个整数： wi每年 i 村子产的木料的块数。（0=wi=10000） vi离 i 村子下游最近的村子。（即 i 村子的父结点）（0=vi=n） divi 到 i 的距离(千米)。（1=di=10000） 保证每年所有的木料流到bytetown 的运费不超过2000,000,000分 50的数据中n不超过20。 【输出格式】输出最小花费，精确到分。 【解析】此题很明显的是一个树形动态规划题。定义FI,J,Fa代表以I节点为根的子树，新增J个木材处理厂，离它最近的木材处理厂是Fa，有如下方程：FI,J,Fa:=MinFLeftI,K,Fa+FRightI,J-K,Fa+CostI*(DisI-DisFa)，FLeftI,K,I+FRightI,J-K-1,Fa仍然用左孩子右兄弟来实现多叉转二叉。需要提前预处理出来一点到其余各点间的距离。program river;const filename=river;type xx=record l,r,w:longint; end; node=record /记录以i为根的所有结点信息 num:longint; v:array1.100 of longint; end;var a:array-1.100 of node; tree:array-1.100 of xx; flag:array-1.100,-1.100,-1.100 of boolean; son,dis:array-1.100 of longint; f:array-1.100,-1.100,-1.100 of longint; /f表示以s为根，建立p个伐木场，且离s最近的点为k时的最优值 map:array-1.100,-1.100 of longint; n,m:longint; procedure init;var i,v:longint;begin readln(n,m); fillchar(son,sizeof(son),$FF); fillchar(tree,sizeof(tree),$FF); fillchar(flag,sizeof(flag),false); fillchar(f,sizeof(f),$7F); fillchar(a,sizeof(a),0); for i:=1 to n do /左孩子右兄弟 begin readln(treei.w,v,mapi,v); if sonv0 then treev.l:=i else treesonv.r:=i; sonv:=i; mapv,i:=mapi,v; inc(av.num); av.vav.num:=i; end;end; procedure pretreatment(x,s:longint); /预处理一点到其余各点间的距离var i:longint;begin disx:=s; for i:=1 to ax.num do /所有与x相连的结点 pretreatment(ax.vi,disx+mapax.vi,x);end; function min(a,b:longint):longint;begin if ab then exit(a) else exit(b);end; procedure dfs(s,k,p:longint); /以s为根，建立p个伐木场，且离s最近的点为k时的最优值var i,j:longint;begin if s=0 then begin dfs(trees.l,s,i); dfs(trees.r,k,p-i-1); fs,k,p:=min(fs,k,p,ftrees.l,s,i+ftrees.r,k,p-i-1); /s处设置伐木场的状态 end; end;end; begin assign(input,filename+.in); reset(input); assign(output,filename+.out); rewrite(output); init; pretreatment(0,0); dfs(0,0,m); writeln(f0,0,m); close(input); close(output);end.【分析】树形动归。首先转换为二叉树。转换后，设fi,j,k表示以i为根的子树最近的伐木场在j件k个伐木场的最小耗费总和，则对于每一个顶点有放伐木场与不放两种方式。fi,j,k=min放伐木场：fi左孩子,i,k+fi兄弟,j,k-k-1不放伐木场：i的运费+fi的孩子,j,