pascal动态规划的一道程序完善题,请大神路过指教,尤其是第四第五两...
发布网友
发布时间：2024-09-29 11:27
共2个回答
热心网友
时间：2024-09-29 14:29
init中主要完成了读入和建图的工作，而可以看出，本程序主要用的是邻接表来建图，
max是比较大小的函数，
solve是解决问题的，采用了递归的方式，vst标记了该点是否走过，枚举当前每个没走过的点，其实就可以认为是往儿子的方向走，而f数组记录的就是结果，f[x,1]一般代表，在以x为根的子树中，选当前点能达到的最大值，所以我们应该给他一个初值就是a[i]，相反的，那f[x,0]就代表，在以x为根的子树中，不选当前点能达到的最大值，所以f[x,0]:=sigma(f[i,1])，f[x,1]:=sigma(f[i,0])i为x的儿子，假设当前节点的所有儿子节点都已经更新完了，那么就可以根据上面两个公式得到当前节点的两个值
在之后就是主程序了，由于截图没有接完，我就都写上吧
主程序流程很简单，读入，解决，输出
所以init();后面应该是solve(root);由于题目给出的是无根树，所以我们要自己设定一个根，之后就是输出，很显然是取f[root,0]和f[root,1]中大的一个（利用max函数）,
所以答案如下
①inc(map[x,0]);
②f[x,1]:=a[x];
③vst[map[x,i]]=0;
④solve(map[x,i]);
⑤f[x,0]+f[map[x,i],1];
⑥f[x,1]+f[map[x,i],0];
没截出来的：
solve(1);
writeln(max(f[1,1], f[1,0]));
end.
没用P一两年了，有错的地方还请指出
热心网友
时间：2024-09-29 14:28
