文件名称：问题分析-动态规划-树型DP经典课件
文件大小：4.26MB
文件格式：PPT
更新时间：2024-05-14 23:11:47
动态规划
问题分析
此题和前面的题有个明显不同的地方，我们关注树的信息，还需要在树上分配资源。
所以我们描述问题时需增加一个维表示要分配的资源,用f[i,j]表示以i为根的树上保留j个边能获得的最多的苹果个数。我们可以用子树的相关特性算出树的相关特性。
f[i,j]=max(f[sonl,j-1]+W[i,sonl],f[sonr,j-1]+W[i,sonr],f[sonl，j’]+f[sonr,j-2-j’]+ W[i,sonl]+W[i,sonr]),1<=j’