当前位置: 首页 > news >正文

[note] slope trick

slope trick 是一个优化二维 DP 的技巧。该二维 DP 需要满足以下条件:

  1. 第二维是连续的;

  2. 若 DP 的第一维固定时,第二维可以看作一个分段一次函数

  3. 这个函数每一段的斜率为整数

  4. 这个函数是凸函数(每一段的斜率是单调的)。

算法思路

考虑如何维护分段凸函数。首先记录这个函数最右端的函数解析式 \(y=kx+b\),然后记录这个函数的斜率变化点,如果函数在某个 \(x\) 值斜率变化了 \(1\),那么就把 \(x\) 加入集合,如果变化不是 \(1\) 就变化多少加多少个 \(x\) 到集合。

比如这个分段函数:

那么我们记录最右边的一次函数 \(y=-2x+8\),然后记录变化点 \(\{-4,-2,-2,2\}\)。(因为斜率在 \(x=-2\) 处从 \(1\) 变成了 \(-1\),因此加入两次。)

slope trick 之所以可以优化 DP,是因为这样维护分段函数可以高效支持某些操作。

1. 两个分段函数相加

两个分段函数相加,得到的分段函数最右端的解析式为原来两个的解析式之和。

如图,加一次函数:

函数绿色(\(y=-2x+8,\{-4,-2,-2,2\}\)),加上一次函数红色(\(y=x+2,\varnothing\)),得到蓝色函数 (\(y=-2x+8+x+2=-x+10\)\(\{-4,-2,-2,2\}+\varnothing=\{-4,-2,-2,2\}\))。

同样常用的还有绝对值函数:

绿色函数(\(y=-2x+8,\{-4,-2,-2,2\}\))加红色绝对值函数(\(y=-x-2,\{-4,-4\}\))得到蓝色函数(\(y=-3x+6,\{-4,-4,-4,-2,-2,2\}\))。

2. 取函数最小/最大值

函数斜率为 \(0\) 的时候,函数取到最小/最大值。有的人说,函数的最小值是一个“尖”,并不存在斜率为 \(0\) 的时候。但注意到我们记录了分段函数的斜率变化点,实际上在“尖尖”上斜率是先由负变成 \(0\) 再到正数的,你可以认为那就是斜率为 \(0\) 的时候。

为了维护这个函数的极值点,我们可以把斜率变化点以函数极值点为边界分成左右两个部分,用堆来维护(参考对顶堆),设左右两个堆为 \(L,R\),最右一段的函数解析式为 \(y=kx+b\),那么我们只要保证 \(R\) 的大小为 \(k\)\(R\) 堆顶的斜率变化点对应的函数值就是函数的极值。

3. 取函数的前缀/后缀的最大/最小值

设原分段函数为 \(f\),那么它的前缀最小/最大值 \(F(i)=\min/\max_{j=1}^{i}f(j)\),后缀最小/最大值 \(G(i)=\min/\max_{j=i}^nf(j)\) 是可以快速的得到的。如图是一个前缀最大值:

图片

由于这是一个凸函数,斜率是单调的,会发现到了斜率为 \(0\) 的那一刻,函数值不变了!

刚刚上一段维护的堆 \(L,R\) 就有用了,只需清空其中一个(比如这次是清空 \(R\)),就可以维护了。

接下来结合例题来解释如何用 slope trick 优化 DP。

例题

P4597 序列 sequence

题目描述

给定一个序列,每次操作可以把某个数 \(+1\)\(-1\)。要求把序列变成非降数列。

对于 \(100 \%\) 的数据,\(1 \le n \le 5 \times {10}^5\)

解题思路

容易设计出二维的 DP 方案:设 \(f_{i,j}\) 表示第 \(i\) 个数改为 \(j\) 所需最少操作数。则:

\[f_{i,j}=\displaystyle\min_{k\le j} f_{i-1,k}+|a_i-j| \]

发现 \(|a_i-j|\) 是一个下凸函数,而 \(f_1\) 也是下凸函数(初始值为绝对值函数),因此下凸函数加下凸函数还是下凸函数,\(f_i\) 均为下凸函数。

于是从 \(f_i\) 推到 \(f_{i+1}\) 就是取前缀 \(\min\) 后再加绝对值函数。由于全程都是取前缀 \(\min\),只用维护堆 \(L\)。最右侧的函数 \(y=kx+b\) ,由于加上绝对值函数 \(k\)\(1\),斜率变化点多 \(2\) 个, \(R\) 堆大小为 \(1\),取完前缀 \(\min\)\(R\) 堆清空,因此每次的操作就是往 \(L\) 堆加 \(2\) 个斜率变化点再弹掉 \(1\) 个。

也可以按对顶堆的维护来理解。

#include<bits/stdc++.h>
using namespace std;
priority_queue<int> q;
int main()
{int n;long long ans=0;scanf("%d",&n);for(int i=1;i<=n;i++){int x;scanf("%d",&x);q.push(x),q.push(x);ans+=q.top()-x;q.pop();}printf("%lld\n",ans);return 0;
}

如果以后遇到其他题目再补充

参考

https://www.cnblogs.com/ruierqwq/p/18017106/slope-trick

https://www.luogu.com.cn/article/bn3a465i

https://www.luogu.me/article/ma1xv4pg

http://www.hskmm.com/?act=detail&tid=32810

相关文章:

  • three自带的框选工具SelectionBox、SelectionHelper
  • 2025年精密磨床/CNC机械加工厂家推荐榜单:涵盖铣床/车床/磨削/多轴/复合加工,铝/不锈钢/钛合金/模具钢/塑料件定制,汽车/医疗/航空航天/机器人零件及模具工装夹具加工
  • 2025 电动缸源头厂家最新推荐榜:剖析国产厂商成本优势与技术实力,附权威选购指南
  • 网络编程实践笔记_4_阿贝云_免费云服务器_简易博客_
  • 10 17
  • 2025年铝单板厂家推荐排行榜,氟碳铝单板,木纹铝单板,冲孔铝单板,外墙铝单板,雕花铝单板,异形铝单板,双曲铝单板公司推荐!
  • 2025 年最新推荐热熔胶源头厂家榜:覆盖书刊装订 / 包装等场景,助企业选高性价比产品
  • 开发日志
  • Gitee 2025:中国开发者生态的崛起与本土化优势
  • C++中的new操作符:new operator、operator new、placement new
  • JavaBean知识总结及范例
  • 2025 年家装管道生产厂家最新推荐排行榜:覆盖云南昆明贵州贵阳四川成都重庆,精选优质 PPR/PVC 管道品牌,解决选购难题
  • 同一设备多账号登录,如何避免消息推送“串门”?
  • 强合规行业DevOps选型:告别工具拼凑,找到真正适配的国产化DevOps方案
  • 大疆无人机RTMP推流至LiveNVR实现web页面实时播放与录像回放,并可以转GB28181协议级联推送给上级监控视频管理平台
  • Character Animator 2025下载安装教程:2D角色动画软件零基础入门,附最新下载安装教程及激活方法
  • 2025年彩钢瓦/镀锌板/折弯件/C型钢/Z型钢/压型瓦/楼承板/次檩条厂家推荐排行榜,专业钢结构安装与定制加工实力解析
  • 2025 年最新金相厂家最新推荐排行榜:涵盖金相磨抛机 / 切割机 / 显微镜 / 抛光机 / 预磨机设备,助力企业精准选择优质品牌
  • 武汉图核科技
  • 完整教程:display ospf peer 概念及题目
  • 2025中国开发者必看:主流代码托管平台本土化能力深度测评
  • 开源数据采集工具 logstash(收集日志)/telegraf(收集指标)
  • 2025年粉末冶金制品厂家推荐排行榜,粉末冶金零件,金属注射成形,结构件,齿轮,轴承公司最新精选
  • 2025 年升降平台车厂家最新推荐口碑排行榜:覆盖多类型产品,聚焦实力厂家,为企业选购提供权威参考剪叉式/手动液压/电动液压升降平台车厂家推荐
  • 供应商图纸协同是什么?主要有哪几个核心原则?
  • 2025 年堆高车厂家最新推荐排行榜:聚焦专利技术、华为等大牌合作案例及国内优质品牌解析手动液压/手动液压/卷筒/油桶堆高车厂家推荐
  • 2025 年最新推荐!编码器源头厂家排行榜:聚焦无磁 / 光学 / 脉冲等多类型产品,精选行业优质企业
  • Excelize 开源基础库发布 2.10.0 版本更新
  • 高效搞定outlook大附件怎么发送的方法与技巧
  • 2025年点胶机厂家权威推荐榜:精密点胶设备、自动化点胶系统、桌面点胶机源头厂家综合实力解析