二分队列+决策单调性优化dp：P6246

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132522515

https://www.luogu.com.cn/problem/P6246

决策单调性

若 $dp_i$ 由 $j$ 转移，则 $dp_{i+1}$ 转移点 $k$ 满足 $k\ge j$

发现决策点满足单调，但遍历的点不满足单调，不能用双指针，考虑二分队列。

二分队列

假设前 $i$ 个已定，只考虑从前转移到后，当前后面那一段必然会分成很多段，段与段直接的转移点必然是单调递增的。

后面的我们可以考虑用单调队列维护。

当加入新决策点 $i+1$ 时，必然是先pop掉尾部一些区间，然后再和当前最末尾的一个共享一个区间

找端点可以二分。