zcmimi's blog
avatar
zcmimi
2020-01-26

对于类似f_i=\min_{j=1}^{i-1}f_j+val(i,j)的方程

比如val(i,j)=a_i\times b_j,同时包含了i,j两个变量,

这样没法直接用单调队列

如果把val(i,j)展开能转化成\frac{y_{j1}-y_{j2}}{x_{j1}-x_{j2}}\le k_i

如果我们将每个决策点看成(x_j,y_j)分布在坐标系上,真正有用的决策点就会形成凸壳(可以使用 单调队列 or 数据结构 来维护)

(其实斜率优化dp也叫凸壳优化dp)

实现主要看例题

关于上下凸壳:

如果是k_i\le\frac ab的形式是下凸壳

k_i\ge\frac ab否则是上凸壳

例题

[HNOI2008]玩具装箱TOY

[APIO2014]序列分割

[APIO2010]特别行动队

LG 2365 任务安排

[SDOI2012]任务安排(所得的直线的斜率不是单调的,需要凸壳二分)

[USACO08MAR]土地征用Land Acquisition

斜率优化
comment评论
Search
search