CodeVS 1380-没有上司的舞会

原题

题目描述 Description

Ural大学有N个职员,编号为1~N.他们有从属关系,也就是说他们的关系就像一棵以校长为根的树,父结点就是子结点的直接上司.每个职员有一个快乐指数.现在有个周年庆宴会,要求与会职员的快乐指数最大.但是,没有职员愿和直接上司一起与会.

输入描述 Input Description

第一行一个整数N.(1<=N<=6000)
接下来N行.第i+1行表示i号职员的快乐指数Ri.(-128<=Ri<=127)
接下来N-1行,每行输入一对整数L,K.表示K是L的直接上司.
最后一行输入0,0.

输出描述 Output Description

输出最大的快乐指数.

样例输入 Sample Input

7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
0 0

样例输出 Sample Output

数据范围及提示 Data Size & Hint

各个测试点1s

题意

给定一棵多叉树n节点的价值以及n-1条父子关系,要你找出若干个节点,使得节点价值之和最大,且每两个节点之间不存在直接的父子关系.

题解

很典型的树形dp,但也可以用记忆化搜索.

首先定义f数组:f[x,1]表示取第x个节点时以x为根的子树的答案;f[x,0]表示不取x时以x为根的子树的答案.

当f[x,0]时,x的儿子有两种选择:取或不取.即f[X,0]=∑max{f[Y_i,0],f[Y_i,1]}//X为Y_i的父亲节点.

当f[x,1]时,x的儿子只能有一种选择:不取.即f[X,1]=∑f[Y_i,0]+r[X]//X为Y_i的父亲节点.

然后找出根节点直接往下搜就行了,而且找根节点不能用repeat!不能用repeat!不能用repeat!要用while!因为repeat不清真!

下面给出两种代码,dp&&记忆化搜索.

dp:

uses math;
var b:array[1..6010,0..6010] of longint;
var r,fa:array[0..6010] of longint;
var f:array[1..6010,0..1] of longint;
var n,i,x,y,p,ans:longint;
function dp(x:longint):longint;
var i,y:longint;
begin
  f[x,1]:=r[x];
  for i:=1 to b[x,0] do
  begin
    y:=b[x,i];dp(y);
    inc(f[x,0],max(f[y,0],f[y,1]));
    inc(f[x,1],f[y,0]);
  end;
end;
begin
  readln(n);
  for i:=1 to n do readln(r[i]);
  for i:=1 to maxlongint do
  begin
    readln(x,y);
    if (x=0)and(y=0) then break;
    inc(b[y,0]); b[y,b[y,0]]:=x; fa[x]:=y;
  end;
  p:=1;while fa[p]<>0 do p:=fa[p]; 
  dp(p);
  writeln(max(f[p,1],f[p,0]));
end.

记忆化搜索:

uses math;
var b:array[1..6010,0..6010] of longint;
var r,fa:array[0..6010] of longint;
var f:array[1..6010,0..1] of longint;
var n,i,x,y,p,ans:longint;
function dfs(x,t:longint):longint;
var i,ans:longint;
begin
  if f[x,t]<>0 then exit(f[x,t]);ans:=0;
  if b[x,0]=0 then if t=1 then exit(r[x]) else exit(0);
  if t=0 then for i:=1 to b[x,0] do inc(ans,max(dfs(b[x,i],1),dfs(b[x,i],0)));
  if t=1 then for i:=1 to b[x,0] do inc(ans,dfs(b[x,i],0));
  if t=1 then inc(ans,r[x]);
  f[x,t]:=ans;exit(ans);
end;
begin
  readln(n);
  for i:=1 to n do readln(r[i]);
  for i:=1 to maxlongint do
  begin
    readln(x,y);
    if (x=0)and(y=0) then break;
    inc(b[y,0]); b[y,b[y,0]]:=x; fa[x]:=y;
  end;
  p:=1;while fa[p]<>0 do p:=fa[p];
  writeln(max(dfs(p,0),dfs(p,1)));
end.

欢迎转载,若转载请注明出处.