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

【学习笔记】slope-trick

[BalticOI 2004] Sequence (Day1)

\(f_{i,x}\) 表示考虑前 \(i\) 个位置,当前放了 \(x\)。转移式如下:

\[f_{i,x} = |a_i - x| + f_{i - 1,x} \]

考虑建坐标系,有点 $(x,f_{i,x})。然后它就相当于给当前的函数加上个 \(y=|a_i-x|\)

\[f_{i,x} = \min\{f_{i,x},f_{i,x-1}\} \]

注意到,我们每次加的是上凸函数,所以 \(f_i\) 也是上凸函数。因此想要实现上面这个转移,只需把斜率 >0 的地方抹平即可。

于是,上述过程可以用一个堆维护函数拐点。

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

相关文章:

  • 10.13-10.19学习做题笔记
  • 2025.10.22
  • yny计数题记录
  • 20232404 2025-2026-2 《网络与系统攻防技术》实验二实验报告
  • 1020302118兰逸霏的第一次作业
  • ubuntu 25.10 修改源 - ldx
  • pytorch学习笔记(1)
  • 20232318 2025-2026-1 《网络与系统攻防技术》实验二实验报告
  • 《中华人民共和国网络安全法》第二十一条这一核心考点
  • 嵌入式软件分层架构设计 - lucky
  • DP 基础题乱做
  • [题解]P4616 [COCI 2017/2018 #5] Pictionary
  • 二三级区别
  • 第九章-Where-1S-tHe-Hacker
  • CF 2023D Many Games
  • 2025.10.22考试记录
  • 2025多校冲刺CSP模拟赛7 题目分析
  • Typora的多端同步方案,如何多台计算机共享md文件?Windows和Mac通过定时执行git来同步markdown文件
  • Trie树
  • Seg T
  • 2025.10.22总结 - A
  • 蛋白表达系统的技术布局与应用
  • 软件工程学习日志2025.10.22
  • CF2077B Finding OR Sum
  • 10月22日
  • OOP-实验二
  • P2272 [ZJOI2007] 最大半连通子图
  • 2025年,哪些微信公众号排版工具能带来效率变革?
  • 我对软件工程的理解
  • PCB线圈生成工具