CF559E Gerald and Path 笔记

显然按端点位置从小往大放，难点在于可能存在一个灯 $r$ 往左射，完全跨越了之前的某个灯 $l<r$，为前面的空隙创造了新的贡献，这个很难统计，原因是 $l$ 对 $r$ 有后效性。

考虑解决这个问题，必然存在一个灯 $i<l$ 对 $r$ 无后效性，也就是说可以把 $(i,r]$ 看作一个独立的块。设 $p=0/1$ 表示向左 / 右射，这个块的左端点是 $max(i+p_i{\mathrm{len}}_i,r-{\mathrm{len}}_r)$，右端点是 $\underset{j\in (i,r]}{max}(j+{\mathrm{len}}_j)$，以上数据都可以在 $i\to n$ 递推 $r$ 时求得。

因此设 $f_{i,j,p_j}$ 表示考虑前 $i$ 个灯，当前所有块的右端点是 $j+p_j{\mathrm{len}}_j$ 的最大覆盖面积，时间复杂度 $O(n^4)$。