主页
搜索
最近更新
数据统计
申请密钥
系统公告
1
/
1
请查看完所有公告
斜率优化
最后更新于 2025-07-31 11:36:12
作者
guoshaoyang
分类
个人记录
复制 Markdown
查看原文
删除文章
更新内容
# 斜率优化 ## 简单介绍 斜率优化是一种优化dp的方法，形如单调队列，但针对的方程不同。 单调队列优化形如$f[i]=max(f[j]+a[i])$的方程，而斜率优化可以将形如$f[i]=max(f[j]*a[i]+b[i])$的方程从$O(n^2)$优化到$O(n)$ ## 做法 ### step1：列出暴力dp的状态转移方程 ### step2：将方程转移为$j$比$k$更优时$\frac{y_j-y_k}{x_j-x_k}<a_i$或$\frac{y_j-y_k}{x_j-x_k}>a_i$的形式 ### step3：$\frac{y_j-y_k}{x_j-x_k}<a_i$则维护下凸壳；$\frac{y_j-y_k}{x_j-x_k}>a_i$则维护上凸壳  ### 维护方法： #### 用直线$y=a_i$切这个凸包，找出截距最大者，实现方法即为从左侧将斜率小于或大于$a_i$的点删除 #### 插入时将插入点两侧破坏凸包性质的点删除即可 ## 几个例题 1. ### [P2365 任务安排 ](https://www.luogu.org/blog/guo-shao-yang-2005/p2365-ren-wu-an-pai) 2. ### [P4027 [NOI2007]货币兑换 ](https://www.luogu.org/blog/guo-shao-yang-2005/p4027-noi2007-huo-bi-yue-huan) 3. ### [P2120 [ZJOI2007]仓库建设 ]() 4. ### [P3195 [HNOI2008]玩具装箱TOY ]()
正在渲染内容...
点赞
0
收藏
0
