hdu 4003 树状DP

September 14, 2015 at 11:56 pm

又是好久没有写点东西了。已经放弃治疗了,没病就没病吧,痛的时候就忍着吧。等以后有了钱去大医院看......总算是把康复的坑填了一点点,心里舒坦了一点点。 题目的大意是说有一棵N个节点(Nu)显然是不能省的,那么递归回来cost[u]也是必然不能省的。所以总的cost[v]绝对不会比一个机器人要省,而且通常来说还要更浪费。所以对于任意的一个节点,和派k个下去M个回来相比,还不如派k-M+1个下去,1个回来,那M-1个人就不闭派下去了,派下去也是多余,还浪费了派下去的代价。 有了这个结论,问题就逐渐明晰了。对于节点v而言,要么派遣i个机器人,且全都不再回来;要么派遣i个机器人,而且有1个机器人回来。我们记dp[u][i]表示节点u实际派遣i个机器人时的最小花费,所谓的实际,是指它可能表示派遣了i个机器人且都不回来,也可能表示了派遣了i+1个机器人且有一个机器人回来。无论如何,u节点消耗了i个机器人。那么正好,dp[u][0]可以用来表示派遣1个机器人而且回来的情况。 这样问题就已经转向了传统的基于分组背包的树状DP模型。每个节点分配一定的质量,以达到最优的价值。这里还有一点要考虑的是为了避免某一组里的物品一件都没有被选(一个机器人都没有派),每次选择这一组的物品之前,我们都优先把最优值赋值为选择了dp[u][0]的情况,这样,如果这正是最优解,那么就选了这个物品;否则,必然要更新,派遣更多的机器人。 至此把自己比较困惑的地方都记录在这里了,如果还有需要补充的以后慢慢补充吧。 #include <iostream> #include <cstdio> #include <cstring> using namespace std; int N, S, K; const int […]

POJ 3162 树状DP

September 3, 2015 at 9:42 pm

好久好久没有写了,正好明天是个大日子,今天就写一篇吧。惯例开始前是吐槽。直到最后才意识到10的6次方是100万而不是10万,因为这个我纠结了一个小时的Runtime Error。好了废话留到日常里,这里还是对题目进行总结。 题目的大意是给定一棵带权的树,然后对树上的每一个点1...N(N < 10^6),都有一个到树上其它点的最远距离,形成数组arr[],要从中找到最大的子区间,使得子区间的最大值和最小值的差不超过给定值M。当然数组arr本身也是需要求的。这题实际上是两道题目或者说是两个算法的组合。所以首先要求数组,也就是树上每一个点到其它点的最远距离。这个问题之前已经遇到过了,不过没有总结过,在这里总结一下,使用的是树状DP。树没有根则很难讨论,所以先任取一点比如1作为树的根,那么对于这棵树的任意节点k,离它最远的点有两种可能,一种是以它为根的子树上的点,一种则是要经过它父节点的点。以它为根的子树上的点到它的最大距离是很好求的,使用最最基本的树状DP一个DFS就可以求出全部节点的这个值,我们记为dp[k][0];重点考察后一种情况,即经过它父节点的那些点,此时这个值就应该等于它到达父节点的值再加上父节点到其它点的最远距离,我们记为dp[k][2],则有 dp[k][2] = dist(k, parent(k)) + (dp[parent(k)][0], dp[parent(k)][2]) 于是最终我们只要求max(dp[k][0], dp[k][2])即可。 这个算法唯一存在的问题是,dp[parent(k)][0]有可能就是经过k的,这样路径就被重复计算了。为此,我们还需要在第一次DFS时记录第二大距离,记为dp[k][1],这样一来,如果发现dist(k, parent(k)) + dp[k][0] == dp[parent(k)][0],我们便选择第二大距离。(第二大距离的记录方式和最大值类似,具体可以看代码)于是得到了 […]