将功补过树形DP

题意/Description：

　　作为间谍专家的Elvis Han受窃取X星球军事中心的秘密情报，他已经成功进入军事中心。但是很不幸的是，在他还没有找到任务需要情报的时候就被发现，这时他清楚他不可能完成任务了，不过还有机会将功补过，也就是得到一些不如任务情报有价值的其他情报，如果得到的情报的总价值大于等于任务情报价值，他也不会受到惩罚。很幸运的是他已经得到的军事中心的地图，情报都是隐藏在各个道路上的，但是他只有时间遍历一定数量的路（时间宝贵呀！还要逃跑。。）现在你做为他的助手，给你地图和每个道路情报价值，希望你分析出，看他能不能将功补过。
　　军事中心是一个严格的二叉树，也就是说，如果有个点可以分道，一定是分出，也只分出2条道路，现在Elvis Han正处在第一个分道处，也就是说树的根结点处。每条道路上都有一个分数，就是这个道路上的情报价值。但是他只有时间走M条路，他的最终情报价值总和就是他所经过的路的情报价值总和（假设他到过的路一定可以把所有情报得到）希望你给出一个方案使得他可以尽量多地获取情报以便将功补过。

读入/Input：

共有N行：
第一行：3个数据：N，M，Q（N表示有多少个路口，包括分道和不分道的路口；M表示他可以有时间走的道路总数；Q表示他的任务情报的价值）
第2~N行：每行3个数据，Xi,Yi,Wi (X，Y表示第I条道路连接的2个路口，W表示这条道路上的情报价值分, 注意，所有数据均在Lonint范围内)

输出/Output：

共包含2行：
第一行：输出TRUE/FALSE（注意大小写），表示他是否可以收集够任务情报价值
第二行：输出一个数据：
如果他可以完成任务，就输出他收集的情报总价值超过任务情报价值的部分。（非负数）
如果不能完成任务，就输出一个数，表示他不能还差多少分才够任务情报价值。（负数）

题解/solution：

这道题故事讲得不错，似乎很烦。可如果是理解了树型DP，就会发现这是二叉苹果树，程序结尾判断一下就OK了。是不是被吓傻了吧。

代码/Code：

var
  f,g,a:array [0..101,0..101] of longint;
  v:array [0..101] of boolean;
  l,r:array [0..101] of longint;
  n,m,q,t:longint;
function max(o,p:longint):longint;
begin
  if o>p then exit(o);
  exit(p);
end;

procedure tree(x:longint);
var
  i:longint;
begin
  if x=0 then exit;
  v[x]:=true;
  for i:=1 to a[x,0] do
    if not v[a[x,i]] then
      begin
        if l[x]=0 then l[x]:=a[x,i]
                  else r[x]:=a[x,i];
      end;
  tree(l[x]);
  tree(r[x]);
end;

procedure main(t,x:longint);
var
  i:longint;
begin
  if (x=0) or (t=0) then
    begin
      f[t,x]:=0;
      exit;
    end;
  if f[t,x]>0 then exit;
  if x=1 then
    begin
      f[t,x]:=max(g[t,l[t]],g[t,r[t]]);
      exit;
    end;
  for i:=0 to x-2 do
    begin
      main(l[t],i);
      main(r[t],x-2-i);
      f[t,x]:=max(f[t,x],f[l[t],i]+f[r[t],x-2-i]);
    end;
  f[t,x]:=f[t,x]+g[t,l[t]]+g[t,r[t]];
  main(l[t],x-1);
  f[t,x]:=max(f[t,x],f[l[t],x-1]+g[t,l[t]]);
  main(r[t],x-1);
  f[t,x]:=max(f[t,x],f[r[t],x-1]+g[t,r[t]]);
end;

procedure init;
var
  i,x,y,w:longint;
begin
  readln(n,m,q);
  for i:=1 to n-1 do
    begin
      readln(x,y,w);
      g[x,y]:=w; g[y,x]:=w;
      inc(a[x,0]); a[x,a[x,0]]:=y;
      inc(a[y,0]); a[y,a[y,0]]:=x;
    end;
  for i:=1 to n do
    if a[i,0]=2 then
      begin
        t:=i;
        break;
      end;
end;

procedure print;
begin
  if f[t,m]>=q then
    begin
      writeln('TRUE');
      write(f[t,m]-q);
      exit;
    end;
  writeln('FALSE');
  write(f[t,m]-q);
end;

begin
  init;
  tree(t);
  main(t,m);
  print;
end.

将功补过 树形DP

将功补过树形DP