广州专业做外贸网站建设,网站友情链接自动上链,自己做的网站注册用户无法收到激活邮箱的邮件,有关小城镇建设的网站一、算法内容
树形动态规划#xff0c;就是在树这一特殊的结构上维护、更新状态的最优解。
通常#xff0c;我们从根结点出发#xff0c;向子结点作深度优先搜索#xff0c;并由其子结点的最优解合并得到该结点的最优解。因此在大多数时候我们都需要借助递归和回溯来帮助…一、算法内容
树形动态规划就是在树这一特殊的结构上维护、更新状态的最优解。
通常我们从根结点出发向子结点作深度优先搜索并由其子结点的最优解合并得到该结点的最优解。因此在大多数时候我们都需要借助递归和回溯来帮助我们完成动态规划的过程。
比如我们现在需要计算子树 u u u 的大小 s i z e [ u ] size[u] size[u]首先遍历其所有子结点 c h i l d s [ u ] childs[u] childs[u]再由子结点的 s i z e size size 累加得到即 s i z e [ u ] ∑ s i z e [ v ] , v ∈ c h i l d r e n ( u ) . size[u]\sum size[v],v\in children(u). size[u]∑size[v],v∈children(u). 有些问题我们还需再次从根结点出发向子结点作深度优先搜索。对于树上的每个结点除根结点以外由父结点的信息父结点合并后的信息除去该孩子的信息就是其余孩子的信息更新该结点的信息。
二、实例分析
1. P1352 没有上司的舞会
1题目大意
这里有一棵总共有 n n n 个结点的树根节点已经确定每一个结点都有一个权值。现在要求选择树上的一些结点使得它们的权值和最大并且满足所选择的所有结点之间都没有父子关系。
2题目分析 很显然每个结点只有选择和不选择两种情况我们可以将这两种状态分别表示为 1 1 1 和 0 0 0。 不难发现一个结点选择与否的结果只会影响到自己上一层的选择情况这就满足了无后效性。 设 u u u 是当前结点 v v v 代表它的子结点。 d p [ u ] [ 0 ] dp[u][0] dp[u][0] 表示不选择 u u u 的最大权重 d p [ u ] [ 1 ] dp[u][1] dp[u][1] 表示选择 u u u 的最大权重。根据所选择结点没有父子关系这一条件很容易得出状态转移方程 d p [ u ] [ 0 ] d p [ u ] [ 0 ] ∑ max ( d p [ v ] [ 0 ] , d p [ v ] [ 1 ] ) , d p [ u ] [ 1 ] d p [ u ] [ 1 ] ∑ max ( d p [ v ] [ 0 ] ) , \begin{aligned} dp[u][0] dp[u][0]\sum\max(dp[v][0], dp[v][1]),\\ dp[u][1] dp[u][1]\sum\max(dp[v][0]), \end{aligned} dp[u][0]dp[u][1]dp[u][0]∑max(dp[v][0],dp[v][1]),dp[u][1]∑max(dp[v][0]), v v v 遍历 u u u 的所有子结点。 可以观察到题目是满足最优子结构的。 时间复杂度为 O ( n ) O(n) O(n)
3核心代码
void dfs(ll u)
{for(ll i p[u]; i ! -1; i e[i].next){ll v e[i].v;dfs(v);dp[u][0] max(dp[v][0], dp[v][1]);dp[u][1] dp[v][0]; }
}2. 二叉苹果树
1题目大意
这里有一棵苹果树它共有 N N N 个结点编号为 1 ∼ N 1 \sim N 1∼N树根编号一定是 1 1 1。我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。现在这颗树枝条太多了需要剪枝。但是一些树枝上长有苹果。给定需要保留的树枝数量求出最多能留住多少苹果。
2题目分析 首先我们需要尊重一下物理原理当某条边被保留下来时从根节点到这条边的路径上的所有边也都必须保留。 不难发现对于每棵子树的情况来说我们只需要记录以它为根且保留 j j j 条边能获得的最大苹果数目即可至于具体它如何保留的并不重要。这就满足了 d p dp dp 的条件。 特别注意对于父节点 u u u 来说如果要保留子结点 v v v 的这颗子树那么 ( u , v ) (u,v) (u,v) 这条边也是一定要保留的。 如此一来我们其实就把该问题转化为了一个 01 01 01 背包问题背包容量是父节点 u u u 总共要保留的边数 j j j物品就是子节点 v v v 要保留的边数 k k k物品的价值就是这棵子树对应的苹果数量以及这条边的苹果数量 设 d p [ u ] [ j ] dp[u][j] dp[u][j] 表示以 u u u 为根的子树上保留 j j j 条边时能获得的苹果数目最大值那么状态转移方程可以表示为 d p [ u ] [ j ] max ( d p [ u ] [ j ] , d p [ u ] [ j − k − 1 ] d p [ v ] [ k ] e [ i ] . w ) dp[u][j]\max(dp[u][j],dp[u][j-k-1]dp[v][k]e[i].w) dp[u][j]max(dp[u][j],dp[u][j−k−1]dp[v][k]e[i].w) 时间复杂度为 O ( n 3 ) O(n^3) O(n3)
3核心代码
void dfs(ll u, ll pre)
{for(ll i p[u]; i ! -1 ; i e[i].next){ll v e[i].v;if(v ! pre){dfs(v, u);for(ll j m; j 1; j--)for(ll k 0; k j - 1; k)dp[u][j] max(dp[u][j], dp[u][j - k - 1] dp[v][k] e[i].w);}}
}三、作业
1.黄题
P1122 最大子树和
P1351 [NOIP 2014 提高组] 联合权值
P1352 没有上司的舞会
2.绿题
P2014 [CTSC1997] 选课
P2015 二叉苹果树
3.蓝题
P3914 染色计数
P3953 [NOIP 2017 提高组] 逛公园
