树型动态规划.pptVIP

树型动态规划;加分二叉树;样例

中序遍历为1,2,3,4,5的二叉树有很多，以下图是其中的三棵，其中第三棵加分最大，为145.;分析;动态规划;选课;分析;样例分析;动态规划;进一步分析;转化为二叉树;动态规划;样例求解过程：初始f(i,0)=0

f(6,1)=6,f(5,1)=max{1,6}=6,f(7,1)=2

f(4,1)=max{1,f(7,1)}=2,f(1,1)=max{1,f(4,1)}=2

f(3,1)=4,f(2,1)=max{1,4}=4

f(5,2)=7

f(7,2)=max{f(5,1)+2}=8

f(4,2)=max{f(7,2),f(7,1)+1}=8

f(1,2)=max{f(4,2),f(4,1)+2}=8

f(2,2)=max{f(1,1)+1,f(3,1)+1)}=5

f(7,3)=9

f(4,3)=max{f(7,2)+1,f(7,3)}=9

f(1,3)=max{f(4,2)+1,f(4,3)}=9

f(2,3)=max{f(1,1)+f(3,1)+1,f(1,2)+1}=9

f(2,4)=max{f(1,3)+1,f(1,2)+f(3,1)+1}=max{9+1,8+4+1}=13

;警卫安排;分析样例

该图有6个区域如图1，安排情况如图2，红色点为安排了警卫。

2号警卫可以观察1，2，5，6；3号警卫可以观察1，3；4号警卫可以观察1，4；

费用：16+5+4=25

;分析;动态规划;procedurework(now:longint);

var

i,j,sum,tmp:longint;

begin

fori:=1tot[now]dowork(w[now,i]);

f[now,0]:=0;

fori:=1tot[now]do

inc(f[now,0],f[w[now,i],1]);

{f[now,1]表示now被儿子照到时照完子树的最小费用}

sum:=0;

fori:=1tot[now]do{儿子必须被照或者安排警卫}

inc(sum,min(f[w[now,i],1],f[w[now,i],2]));

f[now,1]:=maxlongint;

fori:=1tot[now]do{枚举哪个儿子放警卫照到now}

begin

tmp:=sum-min(f[w[now,i],1],f[w[now,i],2])+f[w[now,i],2];

f[now,1]:=min(f[now,1],tmp);

end;

{f[now,2]表示now放警卫时照完子树的最小费用}

f[now,2]:=c[now];

fori:=1tot[now]do{随便儿子有没有被照}

inc(f[now,2],min(min(f[w[now,i],0],f[w[now,i],1]),f[w[now,i],2]));

f[now,1]:=min(f[now,1],f[now,2]);{1包含了2状态，取优值}

end;;begin

assign(input,security.in);reset(input);

readln(n);

fori:=1tondo

begin

read(m);

read(c[m],t[m]);

forj:=1tot[m]do{存储儿子信息}

begin

read(w[m,j]);

inc(d[w[m,j]]);{统计入?度}

end;

end;

forr:=1tondo{找根}

ifd[r]=0thenbreak;

work(r);{动态规划}

assign(output,security.out);rewrite(output);

iff[r,1]f[r,2]then

writeln(f[r,1])

else

writeln(f[r,2]);

end.;programsecurity;

const

maxn=720;

var

d,c,t:array[1..maxn]oflongint;

f:array[1..maxn,0..2]oflongint;

w:array[1..maxn,1..maxn]oflongint;

r,i,j,k,m,n:longi