区间dp（二）

洛谷P1220

P1220 关路灯

请你为老张编一程序来安排关灯的顺序，使从老张开始关灯时刻算起所有灯消耗电最少（灯关掉后便不再消耗电了）。

老张关路灯像区间dp，可以发现他关路灯时不会关关过的中间加的，不然不优。

状态

$dp_{i,j,0/1}$ 表示区间关 $[i,j]$ 最后达到 $i/j$ 的最少功耗。

答案

$$\min(dp_{1,n,0},dp_{1,n,1})$$

连通性问题

tarjan：连通性问题永远的神。

双连通与割点、割边

• 点双连通：在无向图中，删除一个点（不是 $x$ 或者 $y$）后，点 $x$ 和点 $y$ 仍然能够彼此到达，那么称 $x$ 和 $y$ 是点双连通的；

• 边双连通：在无向图中，删除一条边后，点 $x$ 和点 $y$ 仍然能够彼此到达，那么称 $x$ 和 $y$ 是边双连通的；

• 性质 $1$： 点双连通不具有传递性，但边双连通具有传递性；

平衡树

全称是二叉搜索平衡树

二叉搜索树：对于一棵二叉树，每个节点有权值 $val$，任意节点 $x$ 的左子树的权值小于等于 $val_x$，右子树反之。

二叉搜索树的优点：

1. 具有单调性，可以 $log_2$ 的时间查找。
2. 二叉搜索树的中序遍历是单调不减的，可以将下标当做权值，这样一个序列可以映射到一棵二叉搜索树。

为什么需要平衡树？

• 一个序列对应的二叉搜索树不唯一。我们希望找到高度最小的那颗应用。

若一棵二叉树的任意一个结点 $x$，其左右子树高度差不超过 $1$，称为二叉平衡树。