p1180.pas

来自「www.vijos.cn上一些习题的参考源码」· PAS 代码 · 共 81 行

program p1180;
const
    MAXN=400;
    MAXM=400;
type
    tree=record
        v:longint;
        lc,rc:longint;
    end;
var
    t:array[0..MAXN] of tree;
    f:array[0..MAXN] of longint;
    d:array[-1..MAXN,-1..MAXM] of longint;
    n,m,i,j,k,v:longint;
    
    
function dp(i,j:longint):longint;
var
    s,k:longint;
begin
    if d[i,j]>=0 then dp:=d[i,j]
    else begin
        d[i,j]:=dp(t[i].rc,j);
        for k:=1 to j do begin
            s:=dp(t[i].lc,k-1)+dp(t[i].rc,j-k)+t[i].v;
            if s>d[i,j] then d[i,j]:=s;
        end;
        dp:=d[i,j];
    end;
end;

{
错误的做法
注意：在递归体中，不能用局部量存最大，而要用全局量。
function dp(i,j:longint):longint;
var
    s,max,k:longint;
begin
    if d[i,j]>=0 then dp:=d[i,j]
    else begin
        max:=dp(t[i].rc,j);
        for k:=1 to j do begin
            s:=dp(t[i].lc,k-1)+dp(t[i].rc,j-k)+t[i].v;
            if s>max then max:=s;
        end;
        dp:=max;
        dp[i,j]:=max;
    end;
end;
}
begin
    readln(n,m);

    fillchar(f,sizeof(f),0);
    for i:=0 to n do begin
        t[i].lc:=-1;
        t[i].rc:=-1;
        t[i].v:=0;
    end;

    for i:=1 to n do begin
        readln(k,v);
        t[i].v:=v;
        if f[k]=0 then t[k].lc:=i
        else t[f[k]].rc:=i;
        f[k]:=i;
    end;
    
    for i:=-1 to n do begin
        for j:=-1 to m do begin
            if (i=-1) or (j=0) then d[i,j]:=0
            else d[i,j]:=-1;
        end;
    end;
    
    writeln(dp(t[0].lc,m));

end.