codeforces #382 div 2 E. Ostap and Tree (树形dp)

题目链接

题意:将一棵树的若干点染成黑色,要求满足对于任何一个点u,至少存在一个距离其k以内的点v被染成黑色,问染色方案数。

思路:还没完全搞懂。。。记录一些idea…

qq%e5%9b%be%e7%89%8720161201213929

qq%e5%9b%be%e7%89%8720161201214138

 

参考题解

以及:该题解中说的children指的是子树全体。。。坑死好吗。。。坑了一晚上。。气啊。

 

定义状态f[i][j]:以i为根的子树中,能向上贡献j个单位/需要外界往内填补j个单位,方案数

如果是贡献,j为负数

转移的话,考虑不断合并子树,假如说当前处理x为根的子树

不妨把它的儿子按照输入顺序从左往右编号1~N
一开始到x的时候,初始状态f[x][-k] = f[x][1] = 1 
然后不断把儿子的信息合并给x
做法是x与儿子枚举每一个可能的j值然后判断一下这样的状态转移后如何,添加到辅助数组里
最后把辅助数组的值copy给f[x],,

 

 

hdu 1520 Anniversary party (树形dp模板题)

题目链接
题意:一个舞会,每个人有一个val,给出n个人之间的领导和被领导关系,一个人不愿意与他的领导同时参加,问一种安排方案,使得参加的人的val和最大,问这个最大的和是多少。

思路:树形dp模板题。

dp1[v]表示包含v节点的子树的最大值。

dp2[v]表示,不包含v节点的子树的最大值。

下面讲得很清楚。。

Now, similar to array problem, we have to make a decision about including node V in our subset or not. If we include node V, we can’t include any of its children(say v1, v2, …, vn), but we can include any grand child of V. If we don’t include V, we can include any child of V.

So, we can write a recursion by defining maximum of two cases.
.

As we see in most DP problems, multiple formulations can give us optimal answer. Here, from an implementation point of view, we can define an easier solution using DP. We define two DPs, and , denoting maximum coins possible by choosing nodes from subtree of node V and if we include node V in our answer or not, respectively. Our final answer is maximum of two case i.e. .

And defining recursion is even easier in this case. (since we cannot include any of the children) and (since we can include children now, but we can also choose not include them in subset, hence max of both cases).

 

 

whust 2016 warm up C ||codeforces 682 C. Alyona and the Tree (最大连续和,树形dp)

cf682C题目链接

 

题意:给一棵树。。有点权和边权。。。如果一个点v的子树中存在某点u,满足dis(u,v)>a[u],那么点v就非常sad…

dis(u,v)表示点u到v的距离。。。a[u]是u的点权。。现在问最少要删除多少个叶子节点才能使得没有点节点感到sad..

 

思路:dfs一下。。。需要注意的是边权有负数。。。所以类似于区间的最大连续区间和。。。我们也也可以维护在树上的最大连续和。。。只需要如果当前为负就变成0即可。。。

 

 

hdu 2196 Computer (树的直径||树形dp)

hdu2196

题意:给出一棵树。。。求距离每个点的最远距离是多少。。。

思路:最远距离什么的。。能想到树的直径。。。但是有什么关系呢? 我们在求树的直径的时候。。。直径的两个端点是可以知道的。。。如果再从两个端点分别做两次bfs。。。每个点取两个距离的较大值就是答案。。。。?

1A.

 

 

20161201upd:更新一个dp的做法(虽然用树的直径搞貌似要更好想也更直观,不过为了体会dp的思想嘛。。。)

参考题解

 这道题要求的是从树上一点出发的最长路。考虑有根树,不难想到,从树上一点u出发的最长路必然是下述两种情况之一:
(1)第一步向下走,(一直向下,走到某叶子节点)
(2)第一步向上走。
考虑树形DP:
dp[0][u] : 从节点u向下走的最长路径
dp[1][u] : 从节点u向下走的次长路径
这里,次长路径的含义是:与某条选定的最长路径不重合的路径中最长的路径。
dp[2][u] : 从节点u第一步向上走所能获得的最长路径
注意:

考虑如何转移
对于节点u,考虑u的所有子节点v,用dp[0][v]来更新dp[0][u], dp[1][u]。
至于dp[2][u], 仍考虑两种情况:
(1)第二步向下走, 这样便转移到u的父亲节点f第一步向下走的情况。
这时还要考虑用dp[0][f]还是dp[1][f]来更新dp[2][u]:(kk:因为如果第一步向上走,然后又从父亲节点回到当前节点,那么这是无意义,并且等于没有更新向上走的情况,这也是要求次小的原因)如果从f第一步走到u能走出一条从f向下的最长路,就用dp[1][f]来更新dp[2][u],否则用dp[0][f]。
(2)第二步仍向上走,这样便转移到f第一步向上走的情况,即dp[2][f]。

 

 

poj 2342 Anniversary party (基础树形dp)

题目链接

题意:n个人的上下级关系形成一棵树..每一个人有一个val(可正可负),要选若干个人参加一个party,要求是一个人和他的直接上级不能同时在场。问参加party的人最大的val之和。

思路:树形dp入门题。

 

dp[i][0]和dp[i][1]分别表示第i个人不参加和参加party对应的val和。

注意dp转移方程是放在每次dfs之后的回溯位置的。。。

这样做的话访问是从根节点到叶子节点,更新就成了从叶子节点到根节点。。。

联想到数字三角形…其实是一样的。。

sad…dp苦手如我也开始刷dp了吗。。。。