重修Slope Trick，这篇攻略绝对不容错过！
- 内容介绍
- 文章标签
- 相关推荐
本文共计2737个文字，预计阅读时间需要11分钟。
《Slope Trick》算法解析：虽然这个算法在网络上广为流传，但我并未找到太多通俗易懂的讲解blog。因此，本文借鉴了本人口述的理解来撰写。文中所有图片均为本人手绘（若见拙劣，敬请谅解）。绘图真实，但难免有失准确。
Slope Trick 算法存在十余载了，但是我没有找到多少拍手叫好的讲解 blog，所以凭借本人粗拙的理解来写这篇文章。
本文除标明外所有图片均为本人手绘（若丑见谅），画图真的不容易啊 qwq（无耻求赞）。
Slope Trick 是啥？凸代价函数DP优化。
具体哪种题目？AcWing273. 分级
CF713C Sonya and Problem Wihtout a Legend
CF13C Sequence
P2893 [USACO08FEB]Making the Grade G
P4331 [BalticOI 2004]Sequence 数字序列
P4597 序列 sequence
P8118 Mystery
千万题目汇成一句话：
给定长度为 \(N(\le 10^6)\) 的序列 \(A\)，构造一个长度为 \(N\) 的非降序列 \(B\)，最小化 \(S=\sum\limits^N_{i=1}|A_i−B_i|\)，求出 \(S\) 的最小值和 \(B\) 的构造方案。
注意 Slope Trick 不止能够解决这个问题，这个题目只是便于举例而已。
暴力咋做？就是 \(O(n^2)\) 的 DP。
本文共计2737个文字，预计阅读时间需要11分钟。
《Slope Trick》算法解析：虽然这个算法在网络上广为流传，但我并未找到太多通俗易懂的讲解blog。因此，本文借鉴了本人口述的理解来撰写。文中所有图片均为本人手绘（若见拙劣，敬请谅解）。绘图真实，但难免有失准确。
Slope Trick 算法存在十余载了，但是我没有找到多少拍手叫好的讲解 blog，所以凭借本人粗拙的理解来写这篇文章。
本文除标明外所有图片均为本人手绘（若丑见谅），画图真的不容易啊 qwq（无耻求赞）。
Slope Trick 是啥？凸代价函数DP优化。
具体哪种题目？AcWing273. 分级
CF713C Sonya and Problem Wihtout a Legend
CF13C Sequence
P2893 [USACO08FEB]Making the Grade G
P4331 [BalticOI 2004]Sequence 数字序列
P4597 序列 sequence
P8118 Mystery
千万题目汇成一句话：
给定长度为 \(N(\le 10^6)\) 的序列 \(A\)，构造一个长度为 \(N\) 的非降序列 \(B\)，最小化 \(S=\sum\limits^N_{i=1}|A_i−B_i|\)，求出 \(S\) 的最小值和 \(B\) 的构造方案。
注意 Slope Trick 不止能够解决这个问题，这个题目只是便于举例而已。
暴力咋做？就是 \(O(n^2)\) 的 DP。