想这个问题很久了,就是在一维的dp中,满足决策单调性,用单调队列优化。这时每次求出一个fi,考虑i可以用来做那些点的最优决策,假设最后i可以做[l,r]范围内的最有决策点,但是在DP过程中,如果r+1当前的决策点比i好,就直接退出更新,即使r+1的最优决策点是i+1,但是它当前的点(比如可能是f1)却比i要好。这样不就出错了吗?
是四边形不等式还有什么别的性质吗,为什么这样做是可以的?