DP单调队列优化笔记

不敢说完全理解了吧Orz但至少大致知道总体思路了

对于方程形如f(i)=min/max{f(j)+g(i)}, h(i)<=j<i, 其中g(i)的值只与i有关, 且对于a<b<c, h(a)<h(b)<h(c), 换句话说, h(x)单调(不一定严格)递增, 可以使用单调队列优化,下面假定目标是最小化

维护储存”可取用子问题”(也就是所有j的可能取值)的单调队列q, 使得其中f的值单调递增, 对于需要计算的状态f(i), 弹出q头部元素直到q.front.location>=h(i),(很好理解吧),此时f(i)的最优值即为q.front.value+g(i); 然后弹出q尾部元素直到q.back.value<f(i),然后再把f(i)压入队列尾部. 为什么呢? 1. 因为队列是单调的, 所以队头的元素的值肯定为最小化的子问题,而且没有遗漏,因为2.如果一个子状态k被遗漏了,则f(k)<f(t),(t为用这种方法计算出的最优子问题),而且h(i)<=k,但这是不可能的,因为从队头只弹出了h(i)(!<=)k的子状态,所以f(k)必然还在q中;又因为对q的操作保证了队列里子状态f值的单调,所以k必然在t之前,因此获取到的最优子问题应该为k,这和题设矛盾;综上所诉,t为最优的子状态.

一篇好论文:用单调性优化动态规划  1D1D动态规划优化初步

一些基础题:生产产品, 玩具装箱, 烽火传递, Cut the sequence

(肯定还要回来填坑的…表情)