动态规划专题（二）——树形DP
2024-08-25 01:23:41
前言
\(DP\)这东西真的是博大精深啊......
简介
树形\(DP\)，顾名思义，就是在树上操作的\(DP\)，一般可以用\(f_i\)表示以编号为\(i\)的节点为根的子树中的最优解。
转移的时候一般都将信息由子节点转移到父亲节点，也就是将信息从下往上转移。
因此，一般树形\(DP\)都会采用 递归 的形式。
典例1：树上背包
树形\(DP\)中有一种比较经典的题型：树上背包。
其实它的思想与普通背包差不多，关键在于它玄学的时间复杂度。
很多看似\(O(n^3)\)会\(T\)飞（实际上也的确是这样）的题目，可能你用\(O(n^3)\)的树上背包却能跑过（时间复杂度我也不会证），而且不是因为数据水。
可参考一道例题：【洛谷1273】有线电视网。
典例2：带负权树的直径
普通的树的直径可以用\(BFS\)来求，但如果是带负权的，\(BFS\)就会被卡炸（可惜我之前不知道）。
于是就用上了树形\(DP\)。
可参考一道例题：【杂题】访问计划。
几道例题
好吧，\(DP\)好像也没什么东西可讲，这样介绍得还是不够具体。干脆直接看例题来理解一下吧。
第一道例题： 【51nod1299】监狱逃离
这题是一道挺有意思的树形\(DP\)题，我们可以考虑用\(f\)数组来记录每一个节点的状态：完全封死、可以从这个节点到达叶子节点、有犯人可以到达该节点，然后就不难统计出答案了。
第二道例题： 【BZOJ4033】[HAOI2015] 树上染色
比较经典的树形\(DP\)题。这道题最值得注意的地方不是\(DP\)过程，而是注意在一棵有\(n\)个节点的树上将\(m\)个节点染成黑色与将\(n-m\)个节点染成黑色其实是等价的，不加上这个优化就会\(TLE\)。
第三道例题： 【BZOJ1040】[ZJOI2008] 骑士
一道恶心的基环外向树\(DP\)，应该是比较模板的吧。
最新文章
- MySQL入门02-MySQL二进制版本快速部署
- mysql数据库权限及编码
- js中setTimeout()的使用bug
- Java Thread.join()方法
- Visual Studio Online Integrations-Customer support
- cocos2d-x 3.0rc开发指南：Windows下Android环境搭建
- ffmpeg h265
- Swift - .plist文件数据的读取和存储
- myeclipse 之 快捷键
- CSS.05 -- 规避脱标 定位的盒子居中、CSS标签规范、溢出隐藏、内容移除（网页优化）、CSS精灵图
- 2964:日历问题-poj
- WMS二开：外挂页面开发培训
- Mybatis in 查询
- java数据结构面试问题—快慢指针问题
- poj-1330(暴力写的lca)
- php 随机生成数字字母组合
- boost的下载和安装(windows版)
- VMware与Centos系统安装 和重置root密码
- Centos7 在apache+php7环境下 安装 Discuz!X3.4
- async函数对比Generator函数