[CF721E] Road to Home

从前往后依次考虑每个段，不难发现，某个段内要么不表演，要么在不与之前的表演冲突的前提下，尽可能多地表演，即不需要迁就后面的段而让当前的段少表演，否则将后面段的表演移到前面段来，一定不劣。

既然如此，我们只需要 DP 求前 $i$ 段中最多唱多少首歌，设为 $f_i$；在唱最多歌的基础上，最早什么时候结束，设为 $g_i$。

暴力转移是 $O(n^2)$ 的。

考虑满足 $g_j\le l_i-t$ 的转移 $j\to i$，$i$ 段的决策一定是从 $l_i$ 开始唱歌，所以在只从最后一个这样的 $j$ 更新，一定不劣。

而对于 $g_j>l_i-t$ 的所有转移 $j\to i$，每个 $j$ 在整个过程中最多进行一次这样的转移，所以可以暴力做。