bawang51吧 关注:31贴子:3,169
  • 1回复贴,共1

【树形动规】聚会的快乐

只看楼主收藏回复

也叫做没有上司的晚会、没有上司的舞会


IP属地:上海1楼2011-11-01 00:54回复
    var
    i,j,n,final:longint;
    c:char;
    boss,name:array[1..100]of string;
    f,son:array[1..100,0..100]of longint;
    a:array[1..100]of longint;
    function max(a,b:longint):longint;
    begin
    if a>b then
    exit(a);
    exit(b);
    end;
    procedure dp(x:longint);
    var i:longint;
    begin
    f[x,1]:=a[x];
    for i:=1 to son[x,0] do
    begin
    dp(son[x,i]);
    f[x,1]:=f[x,1]+f[son[x,i],0];
    f[x,0]:=f[x,0]+max(f[son[x,i],1],f[son[x,i],0]);
    end;
    end;
    begin
    readln(n);
    for i:=1 to n do
    begin
    repeat
    read(c);
    if c<>' ' then
    name[i]:=name[i]+c;
    until c=' ';
    read(a[i]);
    read(c);
    readln(boss[i]);
    end;
    for i:=1 to n do
    if boss[i]='NOBODY' then
    final:=i
    else
    for j:=1 to n do
    if name[j]=boss[i] then
    begin
    son[j,0]:=son[j,0]+1;
    son[j,son[j,0]]:=i;
    end;
    dp(final);
    writeln(max(f[final,1],f[final,0]));
    end.


    IP属地:上海2楼2011-11-01 00:55
    回复