DP 优化 单调队列优化 如果转移方程是在某个单调递增区间里的最优解，即转移方程有单调性，可以使用单调队列优化。 单调队列优化的本质是方便地维护某个区间的信息。 维护一个双端队列 $q$： 判断队首决策是否合法（在保质期内），若不合法则弹出队首决策。 此时队首决策解释最优选择。 对于队尾决策，如果其比当前决策劣，则将队尾决策出队。最后把当前决策加入队尾。 例题 P6040 「ACOI2020」课后期末考试滑溜滑溜补习班