在补Codeforce的DP时遇到一个比较新颖的题，然后在知乎上刚好 hycc 桑也写了这道题的相关题解，这里是作为学习并引用博客的部分内容
这道题追根溯源发现2016年这个算法已经在APIO2016烟花表演与Codeforces 713C引入，自那之后似乎便销声匿迹了。相关题型数量也较少，因而在这里结合前辈们的工作做一些总结。---by hycc
问题引入：Codeforces 713C题目链接：Here
题意：
给定 \(n\) 个正整数 \(a_i\) ，每次操作可以选择任意一个数将其 \(+1\) 或 \(-1\) ，问至少需要多少次操作可以使得 \(n\) 个数保持严格单增。
数据范围：\(1\le n\le 3000,1\le a_i\le 10^9\)
对我来说这道题其实和曾经写过的 是一样的
这个题是求升序的DP，那么有什么变化呢
不升的条件是：\(a_i -a_j \ge 0\)
升序的条件是：\(a_i -a_j \ge i - j\) 对任意 \(i,j\) 均满足
有没有理解到什么？移项有：\(a_i - i \ge a_j - j\)
所以将 \(a\) 数字变形一下就和POJ3666就是一个题！
【AC Code】
const int N = 3100; int n, m; ll f[N][N], a[N], b[N]; int main() { cin.tie(nullptr)->sync_with_stdio(false); cin >> n; for (int i = 1; i <= n; ++i) { cin >> a[i]; a[i] = a[i] - i; b[i] = a[i]; } sort(b + 1, b + 1 + n); m = 1; for (int i = 2; i <= n; ++i) if (b[i] != b[i - 1]) b[++m] = b[i]; memset(f, 0, sizeof(f)); for (int i = 1; i <= n; ++i) { ll Min = LLONG_MAX; for (int j = 1; j <= m; j++) { Min = min(Min, f[i - 1][j]); f[i][j] = abs(b[j] - a[i]) + Min; } } ll ans = LLONG_MAX; for (int i = 1; i <= m; ++i) ans = min(ans, f[n][i]); cout << ans << "\n"; }当然上面说的思路并不是本篇博客实际想表达，以下才是正文
对于朴素的 \(\mathcal{O}(n^2)\ DP\) ：
一个显然的性质：如果不是“严格单增”而是“严格非降”，那么最终形成的严格非降序列，其中每个元素一定属于 \(\{a_i\}\)
将元素离散化后可以设计 \(f_{i,j}\) 表示到第 \(i\) 个数取 \(j\) 的最少操作数
那么有转移 \(f_{i,j} = \min\limits_{k\le j}f_{i-1,k} + | a_i - j|\) ，记录 \(f_{i-1,*}\) 的前缀 \(\min\) 即可做到 \(\mathcal{O}(n^2)\)
至于如何做到“严格非降”，\(a_{i-1} < a_i,a_{i -1} \le a_i - i,a_{i-1}-(i-1)\le a_i - i\)
于是令 \(a_i = a_i - i\) 即可。
赛后的评论区中出现了一种 \(\mathcal{O}(Nlog\ N)\) 的做法，也就是 Slope Trick算法的第一次现身（？）
Slope Trick：解决一类凸代价函数的DP优化问题当序列DP的转移代价函数为
连续
分段线性函数
凸函数
时，可以通过记录分段函数的最右一段 \(f_r(x)\) 以及其分段点 \(L\) 实现快速维护代价的效果。
如：\(f(x)=\left\{\begin{array}{rr} -x-3 & (x \leq-1) \\ x & (-1<x \leq 1) \\ 2 x-1 & (x>1) \end{array}\right.\)
可以仅记录 \(f_r(x) = 2x - 3\) 与分段点 \(L_f = \{-1,-1,1\}\) 来实现对该分段函数的存储。
注意：要求相邻分段点之间函数的斜率差为 \(1\) ，也就是说相邻两段之间斜率差 \(\ge 1\) 的话，这个分段点要在序列里出现多次。
优秀的性质：
\(F(x),G(x)\) 均为满足上述条件的分段线性函数，那么 \(H(x) =F(x)+G(x)\) 同样为满足条件的分段线性函数，且 \(H_r(x) = F_r(x) + G_r(x),L_H = L_F \bigcup L_G\) 。
该性质使得我们可以很方便得运用数据结构维护 \(L\) 序列。
回顾：Codeforces 713C
转移方程为 \(f_{i,j} = \min\limits_{k\le j}f_{i-1,k} + |a_i - j|\)
令 \(F_{i}(x)=f_{i, x}, G_{i}(x)=\min\limits _{k \leq x} f_{i-1, k}=\min \limits_{k \leq x} F_{i-1}(k)\)
那么有 \(F_i(x) = G_i(x) + |x -a_i|\) ，其中 \(F_i,G_i\) 均为分段线性函数。
\(G_i\) 求的是 \(F_{i-1}\) 的关于函数值的前缀最小值，由于 \(F_{i-1}\) 是一个凸函数，因而其最小值应该在斜率 \(=0\) 处取得，其后部分可以舍去。
而每次由 \(G_i(x)\) 加上 \(|x-a_i|\) ，等价于在 \(L\) 中添加两个分段点 \(\{a_i,a_j\}\)
因而 \(G_i\) 各段的函数斜率形如 \(\{...,-3,-2,-1,0\}\) ，加上 $|x-a_i| $后斜率变为 \(\{...,-3,-2,-1,0,1\}\) ，因而需要删除末尾的分段点。
具体实现中：使用大根堆维护分段点单调有序，每次加入两个 \(a_i\) ，再弹出堆顶元素。
总复杂度 ：\(\mathcal{O}(n\ log\ n)\)