动态规划——斜率优化DP
适用情况
适用于求解最优解(最大、最小)问题。
一般来说,原转移方程可以化为:[三部分——仅与 (i) 有关、仅与 (j) 有关、与 (i) 和 (j) 都有关且是单项式]的,都可以用斜率优化。
形式化的:原式可化为 (dp_i = minlimits_{j in [l,r]}{ mathrm y_j – k_ix_j } – a_i),
其中 (y)、(k)、(x) 均为人为规定与 (dp) 和常数有关的式子。
上凸壳与下凸壳
求解步骤
-
对于任意状态转义方程,设 (A_i),(B_i),使状态转移方程转化为
- (f_i = min(f_j + (A_i – B_j) ^ 2))
-
当 (i) 从 (j) 转移来时,丢掉 (min)
- (f_i = f_j + {A_i} ^ 2 + {B_j} ^ 2 – 2 times A_i times B_j)
-
将仅和 (j) 有关的放在左边,其他的放在右边
- (f_j + {B_j} ^ 2 = 2 times A_i times B_j + f_i – {A_i} ^ 2)
-
仅和 (j) 有关的,是已经求出来的,看做 (y);仅和 (i) 有关的,再附加上常数,是需要求的,看做纵截距;剩下的与 (i) 和 (j) 都有关,将其中仅与 (j) 有关的因式看做 (x),剩余的因式看做斜率
- (y_j = f_j + {B_j} ^ 2)
- (k_i = 2 times A_i)
- (x_j = B_j)
- (b = f_i – {A_i} ^ 2)
-
过点 ((x_j, y_j)) 做一条斜率为 (k_i) 的直线;则 (b = f_i – {A_i} ^ 2) 为该直线的纵截距。
当 (x) 单调递增时:
- 若 $k$ 单调递增或递减,可以使用单调栈维护
- 若 $k$ 无单调性,可以在数组内二分斜率,找到与目标相切的点
已知两个点 (text{A}(x_1, y_1)),(text{B}(x_2, y_2)),则直线 (text{AB}) 斜率为 (dfrac{y_1 – y_2}{x_1 – x_2})
- 小问题:当 (x) 非单调递增呢?
我还没学QwQ
题单
可以参考这个:https://www.luogu.com.cn/training/5352
Reference
[1] https://www.cnblogs.com/littlehb/p/15936381.html
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net