dp优化小结
决策单调性优化dp 很早之前看李煜东蓝书的时候被吓到了，现在来补一下。 前置芝士 决策单调性前提：最优化dp。通俗地讲就是每个状态只能由一个最优地状态转移而来。 决策单调性：状态的最优转移点单调，形式化地说就是。 四边形不等式：有函数 $w(x,y)$，令 $a\le b \le c \le d$，若其满足 $w(a,c)+w(b,d)\le w(a,d)+w(b,c)$ 则称函数 $w(x,y)$ 满足四边形不等式。 决策单调性与四边形不等式的关系：考虑形如 $dp(i)=\min\left\{dp(j)+w(j,i)\right\}$ 的dp，若 $w(j,i)$ 满足四边形不等式，则此dp满足决策单调性。 那么我们怎么通过决策单调性优化dp呢，这有很多种方式。 分治优化决策单调性dp ..
CF200A Cinema 题解
根据题意，若要填的位置已经被占了，那么就按照半径递增的曼哈顿距离圆填入。 我们发现，一个点周围最密集的情况下也只可能有 $k$ 个点，也就是说这个正方形的边长不会超过 $\sqrt k$ 。 所以我们需要找的只有对角线为 $\sqrt{2k}$ 的正方形，用并查集分别维护每一行的联通块的左右边界就可以在 $O(\sqrt{k})$ 的时间复杂度内实现单次查询。 但是当 $m$ 很小的时候，左右边界被填满了，那么就会导致这时候不是一个正方形，需要遍历的行数增多。 但是这时候我们发现中间的一部分已经填满，不需要再填，那么我们也用并查集维护一下，这样可以保证查询的区间一定是一个正方形。 总时间复杂度 $O(k\sqrt{k})$ 。 aclink