一句话理解
斜率优化把 DP 转移变成凸壳询问。
为什么要学
决策单调的线性。
讲解
维护下凸壳，用单调队列或二分斜率。
例子
f[i]=min_j {f[j]+(i-j)^2} 一类。
常见错误
- 不满足凸性。
- 队列维护错增减。
第 556 课
斜率优化 DP
🔴 提高 约 12 分钟
练习 做完再看下一课
斜率优化用于优化特定形式的 DP。
进度保存在本机浏览器里。
左右方向键也可翻课
第 556 课
斜率优化把 DP 转移变成凸壳询问。
决策单调的线性。
维护下凸壳，用单调队列或二分斜率。
f[i]=min_j {f[j]+(i-j)^2} 一类。
斜率优化用于优化特定形式的 DP。
左右方向键也可翻课