pascal题
发布网友
发布时间：2022-05-17 08:06
共3个回答
热心网友
时间：2023-10-14 09:03
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了这道题目的话，你应该熟悉怎么把一棵树转化成二叉树，完后怎么用递规的思想来实现动态规划。所以坚实的基础是很重要的东西，如果没有了基础，什么都是空中楼阁。
程序中已经边读边把二叉树建立好了。
源程序代码：
program bluewater;
type
tree=record
l,r,k:longint;
end;
var
s:string;
i,j,k,l:longint;
n,m:longint;
a:array[0..200] of tree;
b:array[-1..200,0..150] of integer;
f:array[0..200] of longint;
procere treedp(x,y:longint);
var i,j,k,l:longint;
begin
if b[x,y]>=0 then exit;
treedp(a[x].r,y);{只有右子树的情况}
j:=b[a[x].r,y];
for k:=1 to y do{左右子树都有的情况}
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;
if i>j then j:=i;
end;
b[x,y]:=j;
end;
begin
readln(s);
assign(input,s);reset(input);
readln(n,m);
fillchar(f,sizeof(f),0);
for i:=0 to n do
begin a[i].l:=-1;a[i].r:=-1;a[i].k:=-1;end;
{build tree}
for i:=1 to n do
begin
readln(k,l);
a[i].k:=l;
if f[k]=0 then a[k].l:=i
else a[f[k]].r:=i;
f[k]:=i;
end;
{bianjie}
for i:=-1 to n do
for j:=-1 to m do
if (i=-1) or (j=0) then b[i,j]:=0 else b[i,j]:=-1;
{tree dp}
treedp(a[0].l,m);
{output}
writeln(b[a[0].l,m]);
end.
热心网友
时间：2023-10-14 09:04
热心网友
时间：2023-10-14 09:04
