题面

现有一个由 $n$ 个正整数组成的数列，每一次操作可以选择将其中任一元素并对其 $+1$ 或者 $-1$ 。试求最少次数操作，使得最终数组严格递增（最终数组中元素的值可以小于等于 $0$ ）。

数据范围：

$1 \le n \le 3000$

$1 \le a_i \le 10^9$

题目链接

两点性质

首先我们不妨先考虑一个简单一些的情况：我们要求最终数列非严格递增。

那么自然，对于任何一个 $a_i$ ，如果出现了 $a_i > a_j$ 这种尴尬的情况，那么既然要使得操作数尽可能小，我们只需把 $a_i$ 减小至 $a_j$ 或者把 $a_j$ 增大至 $a_i$ 就好了。也就是说，在这个过程中不会有新的值产生（即经过调整后的 $a_i$ 或者 $a_j$ 一定是原数组种出现过的值）。换句话说，在满足操作数最小化的前提下，一定存在一种构造答案数列的方法，使得答案数列中每个元素的值都在原数列中出现过。

具体的证明可以使用数学归纳法。

然而该题要求的是严格递增的数列，我们应如何使用上述性质呢？我们只需要在原数组的基础上把第 $i$ 个元素的值减去 $i$ 就好了。最后再在得出的答案数列基础上把减去的值加回来，那么串中就不会出现相邻两元素值相等的情况了。

所以，后文中的讲解便是针对答案数列非严格递增的讲解了。

动态规划

设计状态

为了方便表述，我们记原数列为 $a$ ，答案数列为 $b$ 。

首先我们来设计状态。

我们用 $i$ 来表示阶段，意味着当前已经处理完了前 $i$ 个元素。可是光有 $i$ 还不够，在转移时我们需要确定 $b_i$ 的值才能确保答案的单调性。那我们不妨把 $b_i$ 也加入状态，令 $dp[i][j]$ 代表已处理完前 $i$ 个元素且 $b_i = j$ 时的最小操作数，不难得出状态转移方程：

$$dp[i][j] = \min\limits_{0 \le k \le j} \{ dp[i - 1][k] \} + |arr[i] - j|$$

由于 $j$ 的取值范围高至 $10^9$ ，因此我们不妨考虑对原数组进行离散化，使得 $j$ 的含义变为原数组中第 $j$ 大的元素。记原数组中第 $j$ 大元素的值为 $val[j]$ ，那么状态转移方程就变为：

$$dp[i][j] = \min\limits_{0 \le k \le j} \{ dp[i - 1][k] \} + |arr[i] - val[j]|$$

朴素的实现方法复杂度高达 $\mathcal{O}(N^3)$ ，这里提供两种优化思路。

优化思路一

我们不妨把所有的 $dp[i - 1][k] \ (0 \le k \le j)$ 称作求解 $\min\limits_{0 \le k \le j} \{ dp[i - 1][k] \}$ 时的决策集合。我们不难发现，随着 $j$ 增加的过程中决策集合中决策因子的数量只会变大而不会减小。因此我们可以考虑用单个变量 $\text{prevMinVal}$ 来维护这个最小值，并在计算每个 $j$ 之前将 $dp[i - 1][j]$ 加入决策集合中（即把 $\text{prevMinVal}$ 更新为其与 $dp[i - 1][j]$ 中的较小值，这样就可以保持 $\text{prevMinVal}$ 代表 $\min\limits_{0 \le k \le j} \{ dp[i - 1][k] \}$ ）。由此我们便可以省掉 $k$ 那一层循环使得复杂度降为 $\mathcal{O}(N^2)$ 。

$$dp[i][j] = \text{prevMinVal} + |arr[i] - val[j]|$$

完整参考代码

优化思路二

我们可以把 $dp[i][j]$ 的含义改为处理完前 $i$ 个元素并且 $b_i \le j$ 时的最小操作数，那么相应地，状态转移方程式为：

$$dp[i][j] = \begin{cases} dp[i - 1][j] = dp[i - 1][j] + |arr[i] - val[i]| & j = 1 \\ \min \{ dp[i - 1][j] + |arr[i] - val[i]|, dp[i][j - 1]\} & j > 1\\ \end{cases}$$

其中 $ dp[i - 1][j] + |arr[i] - val[i]|$ 代表 $b_i = j$ 时的最小操作数，而 $dp[i][j - 1]$ 则代表 $b_i < j$ 时的最小操作数，两者中的最小值也就是 $dp[i][j]$ 啦。细节上为了方便可以把直接把 $dp[0][j]$ 全部初始化为 $0$ 。 这样做也可以省掉 $k$ 那一层循环使得复杂度降为 $\mathcal{O}(N^2)$ 。

完整参考代码

神奇的数学方法

巨犇 woqja125 在评论区中提出了一种代码仅十行且复杂度低至 $\mathcal{O}(nlogn)$ 的神奇解法。

这个方法真的好难理解啊，我也不知道我在写什么（求不打死，逃

首先，我们记 $f_i(x)$ 表示使得 $arr[1 \dots i]$ 单调递增并且 $arr[i] \le x$ 时所需要的最少操作数。我们不难得到求解 $f_i(x)$ 的递推方式（即得到 $f_i$ 与 $f_{i - 1}$ 之间的关系）：

$$f_i(x) = \begin{cases} \min\limits_{Y \le X} \{ |arr[i] - Y| \} & i = 1 \\ \min\limits_{Y \le X} \{ f_{i - 1}(Y) + |arr[i] - Y| \} & i > 1 \\ \end{cases}$$

我们再记 $opt(i)$ 代表使得 $f_i(x)$ 取值最小的 $x$ ，换言之就是使得 $arr[1 \dots i]$ 单调递增且操作次数最小时 $arr[i]$ 的取值。

我们看看 $f_i(x)$ 的定义。我们来研究一下 $i > 1$ 时的递推式：$f_{i -1}(X) + |arr[i] - X|$ ，我们不妨令 $g(x) = |arr[i] - x|$ ，我们作出 $g(x)$ 的图像（大致是一个 “V” 字形，其中 “V” 字底端对应 $g(arr[i])$ ，左边的斜率是 $-1$ ，右边斜率是 $+1$ ）。也就是说，当 $f_{i - 1}(x)$ 加上 $g(x)$ 时，$f_{i - 1}(x)$ 上 $x < arr[i]$ 的部分斜率全部 $-1$ ，而 $x > arr[i]$ 的部分斜率全部 $+1$ 。而我们所要求的 $f_i(x)$ 就是这个新函数的最小值。同时我们也注意到：

1. 在将图像由 $f_{i - 1}(x)$ 变为 $f_i(x)$ 的过程中，引起斜率变化的点增添了 $arr[i]$ 。
2. 在 $x = arr[i]$ 左边，引起 $f_i(x)$ 斜率变化的点有 $i$ 个。

如果 $opt(i) = x$ ，那么对于所有的 $y \ge x$ 都有 $f_i(y) = f_i(x)$ 。不难发现，$f_i(x)$ 也一定是一个关于 $x$ 非严格递减的函数。由于 $y \ge opt(i)$ 时值不再变化，故斜率不再变化，那么 $opt(i)$ 自然也就是斜率为 $0$ 的点，同时也是最后一个引起 $f_i(x)$ 斜率变化的点（即所有引起 $f_i(x)$ 斜率变化点中值最大的）。

这一点发现告诉我们，仅仅通过维护 $f_i(x)$ 上每相邻两点间的斜率我们就可以得到 $opt(i)$ 。我们可以考虑用一个大根堆来保存每一个引起 $f_i(x)$ 斜率变化的点，取堆顶（最大值）便是 $opt(i)$ 。

---

很显然，我们希望求到的答案即 $f_n(opt(n))$ ，同时我们希望知道 $f_i(opt(i))$ 如何从 $f_{i - 1}(opt(i - 1))$ 转移而来。

我们发现：

• 当 $arr[i] \ge opt(i - 1)$ 时，我们实际上不需要对 $arr[i]$ 做任何操作，所以有 $f_i(opt(i)) = f_{i - 1}(opt(i - 1))$ ；
• 当 $arr[i] < opt(i - 1)$ 时，我们显然需要将 $arr[i]$ 增大至 $opt(i - 1)$ ，所以有 $f_i(opt(i)) = f_{i - 1}(opt(i - 1)) + |arr[i] - opt(i - 1)|$ 。

整理一下：

$$f_i(opt(i)) = \begin{cases} f_{i - 1}(opt(i - 1)) & opt(i - 1) \le arr[i] \\ f_{i - 1}(opt(i - 1)) + |arr[i] - opt(i - 1)| & opt(i - 1) > arr[i] \\ \end{cases}$$

当 $i = 1$ 的时候，显然 $f_1(opt(1)) = 0$ 。另外我们不难发现只有满足 $arr[i] < opt(i - 1)$ 的阶段才会对最终的答案造成影响。也就是说：

$$f_n(opt(n)) = \sum\limits_{arr[i] < opt(i - 1), \ 2 \le i \le n}|arr[i] - opt(i - 1)|$$

具体实现时，由于 $f_{i - 1}(opt(i - 1))$ 到 $f_i(opt(i))$ 只与 $opt(i)$ 有关，我们可以把每一个引起斜率变化的值放到一个大根堆中，每次取堆顶就是 $opt(i - 1)$ 。最终我们就可以以 $\mathcal{O}(NlogN)$ 的时间复杂度完成这道题了：

• 当 $arr[i] \ge opt(i - 1)$ 时，我们只需将 $arr[i]$ 加入大根堆中（新增一个引起函数斜率变化的点）；
• 当 $arr[i] < opt(i - 1)$ 时，我们显然需要把 $arr[i]$ 变成 $opt(i - 1)$ （也就是堆顶）。在此之后，我们需要弹出堆顶，并将 $arr[i]$ 两次加入大根堆（对不同的 $i$ ， $opt(i)$ 是可以有重值的）。这样维护了之前提到的性质 “在 $x = arr[i]$ 左边，引起 $f_i(x)$ 斜率变化的点有 $i$ 个”（因为这事实上等效于将 $[-\infty, arr[i]]$ 的斜率 $-1$ ，$[arr[i], opt(i - 1)]$ 的斜率 $+1$ ）。

完整参考代码