浅谈斜率优化

墨蓝 2023-06-05 08:55 19阅读 0赞

# DP模型 #

形如\\(f(i)=\\max \\\{f(j)+w(i,j)\\\}\\quad(1\\le j<i)\\)的dp状态转移方程，朴素的转移时间复杂度为\\(O(n^2)\\),如果\\(w\\)中不含i，j的乘积项，并且当i固定时\\(w\\)具有单调性，那么我们可以用单调队列优化转移，时间复杂度为\\(O(n)\\)

如果\\(w\\)中含有i，j的乘积项，我们使用斜率优化优化状态转移

# 【HNOI2008】玩具装箱 #

根据题意，状态转移方程为\\(f\[i\]=\\min\\\{f\[j\]+(sum\[i\]-sum\[j\]+i-j-L-1)^2\\\}\\quad(j < i)\\)

这个方程是\\(O(n^2)\\)的，我们考虑有斜率优化

令\\(a\[i\]=sum\[i\] + i,\\ b\[i\]=sum\[i\]+i+L+1\\)

假设\\(j\\)为决策点，那么  
\\\[ f\[i\]=f\[j\]+(a\[i\] - b\[j\])^2 \\\\ f\[i\]=f\[j\]+a\[i\]^2+b\[j\]^2-2\\times a\[i\]\\times b\[j\]\\\\ f\[j\]+b\[j\]^2=2\\times a\[i\]\\times b\[j\]+f\[i\]-a\[i\]^2 \\\]  
我们将这个式子看做一条直线\\(y=kx+b\\)，其中\\(y=f\[j\]+b\[j\]^2\\)，\\(k=2a\[i\]\\)，\\(x=b\[j\]\\)，\\(b=f\[i\]-a\[i\]^2\\)

对于每一个\\(i\\)，这条直线的斜率确定，\\(f\[i\]\\)的转移转化为：当直线过\\(P(b\[j\],f\[j\]+b\[j\]^2)\\)时，截距加上\\(a\[i\]^2\\)

题目的答案事实上是找到最小的截距

所以，我们将上述直线从下往上平移，经过的第一个决策点就是截距最小的点

所以，可能成为决策点的P组成了一个下凸包，凸包的斜率是递增的，而且目标直线的斜率也是递增的

显然，决策点就是斜率第一个大于目标直线的点

我们用一个单调队列维护一下凸包

对于队首：如果队首前两个点的直线的斜率小于目标直线，那么直接出队

对于插入：如果即将插入的点与队尾的点的直线斜率小于队列后两个点的直线斜率，那么队尾弹出

那么我们就完成了了斜率优化

# 【CF1083E】 The Fair Nut and Rectangles #

分析状态转移方程可知，我们要求出最大的截距，所以我们用单调队列维护一个上凸壳即可

# 【APIO2014】序列分割 #

分析状态转移方程可知，我们要求出最大的截距，并且直线的斜率是负的，凸壳位于第三象限，这样维护一个下凸壳即可

转载于:https://www.cnblogs.com/shl-blog/p/11628306.html

发表评论取消回复

表情：

评论列表（有 0 条评论，19人围观）

还没有评论，来说两句吧...

相关阅读

相关浅谈斜率优化

DP模型形如\\(f(i)=\\max \\\{f(j)+w(i,j)\\\}\\quad(1\\le j<i)\\)的dp状态转移方程，朴素的转移时间复杂度为\\(O

墨蓝/ 2023年06月05日 08:55/ 0 赞/ 20 阅读

相关 App性能优化浅谈

前言前段时间给公司的小伙伴们进行了关于app性能优化的技术分享，这里我稍微整理一下也给大家分享一下，关于性能优化这个话题很大，涉及面可以很广，也可以很深入，本人能力有限

曾经终败给现在/ 2022年08月18日 11:50/ 0 赞/ 306 阅读

相关浅谈前端性能优化

1、什么是前端性能优化？从用户访问资源到资源完整展现在用户面前的过程中，通过技术手段和优化策略，缩短每个步骤的处理时间从而提升整个资源的访问和呈现速度。 2、为什么

╰半夏微凉°/ 2022年06月17日 03:37/ 0 赞/ 299 阅读

相关浅谈数据库优化

谈到数据库优化，那么重点一定是索引 > 首先，索引坦白了讲就是和书的目录一个道理，查找更快（快很多）。首先，数据库尽量不要存null，当我们进行where nu

太过爱你忘了你带给我的痛/ 2022年06月10日 09:05/ 0 赞/ 255 阅读

相关浅谈索引优化

索引的优化一:应用场景(千万条数据) 说起提高数据库性能，索引是最物美价廉的东西了。不用加内存，不用改程序，不用调sql，只要执行个正确的’create index’，查

男娘i/ 2022年06月05日 10:58/ 0 赞/ 259 阅读

相关 Print Article(hdu - 3507)之浅谈如何用斜率优化巧解DP

目录前言斜率优化一般常见方程题目斜率优化之推理斜率优化之下凸包斜率优化之凸包判断斜率优化之参考代码后记 -----------------

太过爱你忘了你带给我的痛/ 2022年03月26日 03:22/ 0 赞/ 152 阅读

相关浅谈webpack优化

webpack优化方案 1. 优化开发体验 1-1. 加快构建速度 ① 缩小文件搜索范围由于 Loader 对文件的转换操作很耗时

水深无声/ 2021年11月05日 09:10/ 0 赞/ 426 阅读

相关「斜率优化」学习笔记

当动态规划的状态数为\\(O(n)\\)，每个状态的转移数也是\\(O(n)\\)时，称这种动态规划为1D1D动态规划。对于这种问题，朴素做法是\\(O(n^2)\\)的。

我就是我/ 2021年10月29日 15:38/ 0 赞/ 443 阅读

相关浅谈SQL优化

SQL优化方案在我们书写SQL语句的时候，其实书写的顺序、策略会影响到SQL的性能，虽然实现的功能是一样的，但是它们的性能会有些许差别。因此，下面就讲解在书写SQL

末蓝、/ 2021年09月17日 06:48/ 0 赞/ 433 阅读

相关浅谈 Vue 项目优化

前几天看到大家说 vue 项目越大越难优化，带来很多痛苦，这是避免不了的，问题终究要解决，框架的性能是没有问题的，各大测试网站都有相关数据。下面进入正题基础优化所谓

分手后的思念是犯贱/ 2021年09月14日 04:52/ 0 赞/ 480 阅读