这似乎是今天本蒟蒻发的第inf个帖了吧

决策单调性优化$dp$:

首先，我们$l=1,r=1$，压入区间$[1,n,0]$($1-n$这个区间的决策点为$0$)

①转移；

直接按照状态转移方程转移，特判不可行的情况

②l++(队头调整)；

如果整个区间都没了，直接去掉队头；否则队头的左端点加一

③r--(队尾出队)；

右边有一些决策不好，直接去掉

如果把所有决策都去了，那么就新加入一个三元组$(i+1,n,i)$

④二分拆区间；

如果这个区间本身很好，就不管它

否则二分找到分界点，拆开这个区间

⑤压入新区间；

如果$k$不大于$n$才能压入

压入的是$(k,n,i)$

每步一个特判，请注意！