ZROI 学习笔记——Week 2
都别催！！！等我有时间了例题和详细讲解都会补回来的！！！
7.27 Day 1 - 区间 DP & 树形 DP
区间 DP
- 合并：即将两个或多个部分进行整合，当然也可以反过来；
- 特征：能将问题分解为能两两合并的形式；
- 求解：对整个问题设最优值，枚举合并点，将问题分解为左右两个部分，最后合并两个部分的最优值得到原问题的最优值。
树形 DP
- 经典问题：树的直径
- 换根 DP：《取消父子关系，再给人家当儿子》
wcy 硬垒
算法介绍：wcy 硬垒
命名原因：wcy 把扫描线合理外推，运用到甚至可能不算扫描线的方面，并称其为“扫描线的思想”，惨遭某人批评，于是，wcy 硬垒应运而生。
算法内容：类似扫描线的思想，将点集（区间端点集）按照某个坐标排序后分层，按层次从低到高逐层解决或层层合并，转换为一个或多个单层问题，再进行 DP 或查询操作。
例题：CF1372E，暑假模拟赛 D1T2。
(虽然这两道题 wcy 自己都没有把正解完全想出来，但由于他的想法与题解十分接近，他固执的称这就是所谓的 wcy 硬垒。)