dp优化小结
决策单调性优化dp 很早之前看李煜东蓝书的时候被吓到了，现在来补一下。 前置芝士 决策单调性前提：最优化dp。通俗地讲就是每个状态只能由一个最优地状态转移而来。 决策单调性：状态的最优转移点单调，形式化地说就是。 四边形不等式：有函数 $w(x,y)$，令 $a\le b \le c \l…
CF200A Cinema 题解
根据题意，若要填的位置已经被占了，那么就按照半径递增的曼哈顿距离圆填入。 我们发现，一个点周围最密集的情况下也只可能有 $k$ 个点，也就是说这个正方形的边长不会超过 $\sqrt k$ 。 所以我们需要找的只有对角线为 $\sqrt{2k}$ 的正方形，用并查集分别维护每一行的联通块的左右边…