1D1D

典型模型： $$dp_i=\min\limits_{i-k+1 \leq j \leq i} dp_{j-1}+max(a_j,a_{j+1},\dots,a_i)$$ 这类问题有简单的 $nlogn$ 做法，但是对于部分问题则要求我们使用线性做法。一个用烂的做法是用均摊的数据结构去维护上面的转移区 ......