[CF559E] Gerald and Path

从左到右依次考虑所有端点，进行决策。

为了便于处理线段重叠的情况，设 DP 状态 $f_{i,j}$ 为前 $i$ 个端点的所有决策中，覆盖点 $j$ 以左的部分最多有多长。

分类讨论这 $i$ 条线段，是否覆盖到了 $a_i$ 以右的点。

没有覆盖的话，$j=a_i$ 时的答案应该由 $j=a_i-l_i$ 的答案转移而来。

否则我们枚举右端点最靠右的线段 $k$，显然此时 $(k,i]$ 中的线段向右延伸一定不优于全部向左延伸。设 $(k,i)$ 中所有线段向左延伸的左端点为 $t$，那么 $j=a_k+l_k$ 时的答案应当由 $j=t$ 的答案转移而来。

此时我们处理完了 $j$ 恰好落在被覆盖的最靠右的点的情形。那么对此从左向右令 $f_{i,j}\leftarrow\max(f_{i,j},f_{i,j-1})$，再从右向左地依次令 $f_{i,j}\leftarrow\max(f_{i,j},f_{i,j+1}-1)$。即可。这样做等效于将 $j$ 处的值改为 $\max(\max_{k\le j}f_{i,k},\max_{k>j}f_{i,k}-k+j)$，如果 $i$ 没有被覆盖，那么会取前者，否则会取后者（因为 $f_{i,j+1}-f_{i,j}\in[0,1]$）。