uva 1407 Caves (树形背包dp)

本文出自 http://blog.csdn.net/shuangde800

题目链接: uva-1407 hdu-3672

题意

一棵n个节点的树,树的边有正整数权,表示两个节点之间的距离.你的任务是回答这样的询问:从跟节点出发,走不超过x单位的距离,
最多能经过多少节点?同一个节点经过多次, 只能算一个.

思路

这题同样是多天前看的, 在今天才想出解法的. 动态规划就是这么有意思 :)
遍历n个节点, 有两种情况, 第一种是遍历完之后不回到出发点, 第二种是要回到出发点.
两种都可能会重复经过某些边, 但是显然还是第二种遍历的花费会更大
在这一题中, 遍历之后不需要回到出发点.

f(i, j, 0): 表示遍历子树i的j个节点, 不用回到i点的最少花费
f(i, j, 1): 表示遍历子树i的j个节点, 最终又回到i点的最少花费

f(i, j, 1) = min{ min{ f(i, j-k, 1) + f(v, k, 1) + 2*w | 1<=k<j } | v是i的儿子节点}

f(i, j, 0) = min{ min{ min{f(i,j-k,1)+f(v,k,0)+w, f(i,j-k,0)+f(v,k,1)+2*w} | 1<=k<j } | v是i的儿子节点 }

代码

<script src="https://code.csdn.net/snippets/685.js" type="text/javascript"></script>