【学习笔记】斜率优化 DP

算法介绍在平时的 DP 过程中我们可能会遇到这样的 DP 式子min⁡−−(×)dpi​ji−xmini−y​(dpj​ai​×bj​ci​dj​M)单调队列优化 DP 拼劲全力无法战胜只能请它大哥出场了。推导一动态规划当然要考虑最优决策点的位置呀所以我们假设现在有1,2(12)j1​,j2​(j1​j2​) 两个决策点如果2j2​更优秀应该满足的条件是酱紫的2×22≤1×112×22≤1×11−×(1−2)≤(11)−(22)dpj2​​ai​×bj2​​ci​dj2​​Mdpj2​​ai​×bj2​​dj2​​−ai​×(bj1​​−bj2​​)​≤dpj1​​ai​×bj1​​ci​dj1​​M≤dpj1​​ai​×bj1​​dj1​​≤(dpj1​​dj1​​)−(dpj2​​dj2​​)​如果1−2≠0bj1​​−bj2​​0那么我们就会得到这个不等式≥(11)−(22)1−2ai​≥bj1​​−bj2​​(dpj1​​dj1​​)−(dpj2​​dj2​​)​如果1−20bj1​​−bj2​​0你可以认为上面那个值是∞∞。这里我们令(),()X(i)bi​,Y(i)dpi​di​那么不等式变为≥(1)−(2)(1)−(2)ai​≥X(j1​)−X(j2​)Y(j1​)−Y(j2​)​将((),())(X(j),Y(j)) 作为j 的对应点放入平面。如果1j1​与2j2​构成的直线斜率小于等于ai​这里1,2j1​,j2​作为决策点出现那么2j2​优于1j1​否则1j1​优于2j2​。假设∈[−,−]j∈[i−x,i−y]那么下图的点就是对应到平面上的散点我们把目光放到,,A,B,C 三个点上这里假设,A,B 构成的直线斜率是1k1​,B,C 构成的直线斜率是2k2​此处我们钦定12k1​k2​。如果21≤k2​k1​≤ai​那么C 是最优点如果2≤1k2​≤ai​k1​那么C 是最优点如果21ai​k2​k1​那么A 是最优点也就是说B 永远不会存为最优点就要淘汰掉太馋人哦不太残忍了。同样的道理这里看似有这么多点但实则只有下凸包上的点会用到又因为下凸包的斜率是单调递增的如果j 前面的斜率都是小于等于ai​后面的斜率都是ai​那么j 就是当前的最优决策点。那不对呀上凸包怎么能被忽略呢所以如果上面不等式是≤(1)−(2)(1)−(2)ai​≤X(j1​)−X(j2​)Y(j1​)−Y(j2​)​的话那么决策点就在上凸包上啦推导二TA 回来了min⁡−−(×)dpi​ji−xmini−y​(dpj​ai​×bj​ci​dj​M)先假装看不见min⁡min×dpi​dpj​ai​×bj​ci​dj​M进一步−×−−dpj​dj​−ai​×bj​dpi​−ci​−m令,−,,−−ydpj​dj​,k−ai​,xbj​,bdpi​−ci​−m那么上式就变成了ykxb此时最小化dpi​就相当于最小化b。怎样移向呢看法则,x,y 与i 无关,k,b 与j 无关b 中要有我们要求的dpi​我们把每一个,x,y 当成一个点对应到平面上这就是我们的决策点。接着我们用−[]k−a[i] 的直线去对准每一个点如图看看哪条直线的截距也就是b最小就好了。你看最优决策点的位置不变说明最优决策点还是在下凸包的斜率单峰处。当然最大化b 就是上凸包。总结其实它们本质是相同的可以相辅相成地来理解。接下来明白了最优决策点在什么位置那该怎么快速地找最优决策点呢如果状态转移决策具有决策单调性放在刚才的例子里就是∀,∀ij,ai​aj​即二次项系数ai​单调递增此时随着和斜率比较的ai​的不断增加由于下凸包上的点单调递增ai​卡到下凸包上的点一定越来越靠后则可以用单调队列维护凸包上的点单调队列返厂啦。如果不具有决策单调性则根据凸包的单调性二分即可。例题讲解P3195 [HNOI2008] 玩具装箱题目分析状态设计定义dpi​表示对于前i 个玩具若i 作为所属分组的最后一个玩具求总的最小花费。转移方程min⁡1−1{(−(1)(∑)−)2}dpi​j1mini−1​{dpj​(i−(j1)(kj∑i​Ck​)−L)2}设∑1,1Si​∑j1i​Cj​,ML1则转移方程变为min⁡1−1{(−−)2}dpi​j1mini−1​{dpj​(Si​−Sj​−M)2}拆开min⁡1−1{222−2−22}dpi​j1mini−1​{dpj​Si2​Sj2​M2−2Si​Sj​−2Si​M2Sj​M}发现了22Si​Sj​因此斜率优化必定了。状态初始化00dp0​0。答案就是dpn​。如果当前状态为dpi​若存在决策点1,2(12)j1​,j2​(j1​j2​)且2j2​优于1j1​则22222−22−222≤12122−21−221222−2222≤112−21212(1−2)≥(11221)−(22222)∵≥1,1≠2∴1−2≠02≥(11221)−(22222)1−2dpj2​​Si2​Sj2​2​M2−2Si​Sj2​​−2Si​M2Sj2​​Mdpj2​​Sj2​2​−2Si​Sj2​​2Sj2​​M2Si​(Sj1​​−Sj2​​)2Si​​≤dpj1​​Si2​Sj1​2​M2−2Si​Sj1​​−2Si​M2Sj1​​M≤dpj1​​Sj1​2​−2Si​Sj1​​2Sj1​​M≥(dpj1​​Sj1​2​2Sj1​​M)−(dpj2​​Sj2​2​2Sj2​​M)∵Ci​≥1, j1​j2​∴Sj1​​−Sj2​​0≥Sj1​​−Sj2​​(dpj1​​Sj1​2​2Sj1​​M)−(dpj2​​Sj2​2​2Sj2​​M)​​令(),()[]22X(j)Sj​, Y(j)dp[j]Sj2​2Sj​M得2≥(1)−(2)(1)−(2)2Si​≥X(j1​)−X(j2​)Y(j1​)−Y(j2​)​满足此条件时有2j2​优于1j1​则根据原理处的推导只需要维护∈[1,−1]j∈[1,i−1] 对应的点集((),())(X(j),Y(j)) 的下凸包即可。又由于Si​单调递增所以状态转移具有决策单调性可以用单调队列维护即不是i 的最优决策点的点不会再是1i1 的最优决策点。注意单调队列中维护凸包上的点对应的j。维护的点不应存在三点共线而应当只维护两端点。单调队列中应保证至少有两个点再求斜率deque 难以实现且常数大建议使用手写队列。维护凸包比较斜率时建议不要使用除法容易被卡精度交叉相乘是更好的选择。同时0≥0a​≥cb​交叉相乘后恒成立这难道不正是我们一直在找的0∞0a​∞ 的可行实现方案吗代码实现cpp#include bits/stdc.h#define int long longusing namespace std;const int N 5e4 10;int n, L, c[N];int dp[N], s[N], a[N], b[N];int q[N], h 1, t 1;int X(int p) { return b[p]; }int Y(int p) { return dp[p] b[p] * b[p]; }double slope(int a, int b) {if (X(a) X(b)) {if (Y(a) Y(b)) return 0; // 斜率无法比较if (Y(a) Y(b)) return -1e18; // 斜率为负无穷else return 1e18; // 斜率为正无穷}return (Y(a) - Y(b)) * 1.00 / (X(a) - X(b));}signed main() {scanf(“%lld%lld”, n, L);for (int i 1; i n; i) scanf(“%lld”, c[i]), s[i] s[i - 1] c[i];for (int i 0; i n; i) a[i] s[i] i, b[i] s[i] i L 1;q[1] 0;for (int i 1; i n; i) {// 由于凸包的斜率一定单调递增于是把队头斜率小于 2 * a[i] 的点删除while (h t slope(q[h], q[h 1]) 2 * a[i]) h;int j q[h];dp[i] dp[j] (a[i] - b[j]) * (a[i] - b[j]); // 状态转移方程// 把队尾的斜率小于当前点的坐标删除放入当前点while (h t slope(q[t - 1], q[t]) slope(q[t], i)) t–;q[t] i;}printf(“%lld\n”, dp[n]);return 0;}P2365 [IOI 2002] 任务安排题目分析状态设计用,dpi,j​表示前i 个任务分成j 组i 为第j 组最后一个任务完成所有任务所需时间的最小值。转移方程,min⁡−1≤,−1∑1×min⁡−1≤,−1×∑1dpi,j​​j−1≤kimin​dpk,j−1​pk1∑i​timj​×fk​sj−1≤kimin​dpk,j−1​timj​×pk1∑i​fk​s​优化一下假设∑1,∑1Ti​∑j1i​timj​,Fi​∑j1i​fj​。则上式变为,min⁡−1≤,−1×(−)dpi,j​j−1≤kimin​dpk,j−1​timj​×(Fi​−Fk​)