UC知道一题pascal的动态规划，写思路和程序！！！！
来源：百度知道 编辑：UC知道 时间：2024/07/06 14:31:58
Description
<问题背景>
作为间谍专家的Elvis Han受窃取X星球军事中心的秘密情报，他已经成功进入军事中心。但是很不幸的是，在他还没有找到任务需要情报的时候就被发现，这时他清楚他不可能完成任务了，不过还有机会将功补过，也就是得到一些不如任务情报有价值的其他情报，如果得到的情报的总价值大于等于任务情报价值，他也不会受到惩罚。很幸运的是他已经得到的军事中心的地图，情报都是隐藏在各个道路上的，但是他只有时间遍历一定数量的路（时间宝贵呀！还要逃跑。。）现在你做为他的助手，给你地图和每个道路情报价值，希望你分析出，看他能不能将功补过。
<问题描述>
军事中心是一个严格的二叉树，也就是说，如果有个点可以分道，一定是分出，也只分出2条道路，现在Elvis Han正处在第一个分道处，也就是说树的根结点处。每条道路上都有一个分数，就是这个道路上的情报价值。但是他只有时间走M条路，他的最终情报价值总和就是他所经过的路的情报价值总和（假设他到过的路一定可以把所有情报得到）希望你给出一个方案使得他可以尽量多地获取情报以便将功补过。
Input
在输入文件inform.in中，共有N行：
第一行：3个数据：N，M，Q（N表示有多少个路口，包括分道和不分道的路口；M表示他可以有时间走的道路总数；Q表示他的任务情报的价值）
第2~N行：每行3个数据，Xi,Yi,Wi(X，Y表示第I条道路连接的2个路口，W表示这条道路上的情报价值分)
（注意：要访问子结点必须先要访问他的根结点）
Output
在输出文件inform.out中，共包含2行：
第一行：输出TRUE/FALSE（注意大小写），表示他是否可以收集够任务情报价值
第二行：输出一个数据：
如果他可以完成任务，就输出他收集的情报总价值超过任务情报价值的部分。（正数）
如果不能完成任务，就输出一个数，表示他还差多少分才够任务情报价值。（负数）
Sample Input
<样例输入1&
树形DP，要睡觉了，简单说一下
决策是向左走或者向右走
最好使用记忆化搜索
program jiandie;
type
tr=record
l,r,x:longint;
end;
var
n,m,i,q,ans:longint;
tree:array[1..100]of tr;
f:array[1..100]of longint;
procedure init;
var
i:longint;
begin
readln(n,m,q);
for i:=1 to n-1 do
readln(tree[i].l,tree[i].r,tree[i].x);
end;
function max(a,b:longint):longint;
begin
if a>b then exit(a);exit(b);
end;
function dp(x,y:longint):longint;
begin
if y>m then exit(0);
if f[x]<>-maxlongint then exit(f[x]);
f[x]:=max(dp(tree[x].l,y+1),dp(tree[x].r,y+1))+tree[x].x;
exit(f[x]);
end;
begin
init;
for i:=1 to n do f[i]:=-maxlongint;
if m=1 then ans:=tree[1].x
else if m=0 then ans:=0
else
begin
f[1]:=max(tree[1].x+dp(tree[1].l,2),tree[1].x+dp(tree[1].r,2));<