Codeforces 713C - Sonya and Problem Wihtout a Legend

Author Avatar
Jimmy Zhang May 08, 2018
  • Read this article on other devices

题面

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

数据范围:

1n30001 \le n \le 3000

1ai1091 \le a_i \le 10^9

题目链接

两点性质

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

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

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

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

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

动态规划

设计状态

为了方便表述,我们记原数列为 aa,答案数列为 bb

首先我们来设计状态。

我们用 ii 来表示阶段,意味着当前已经处理完了前 ii 个元素。可是光有 ii 还不够,在转移时我们需要确定 bib_i 的值才能确保答案的单调性。那我们不妨把 bib_i 也加入状态,令 dp[i][j]dp[i][j] 代表已处理完前 ii 个元素且 bi=jb_i = j 时的最小操作数,不难得出状态转移方程:
dp[i][j]=min0kj{dp[i1][k]}+arr[i]jdp[i][j] = \min\limits_{0 \le k \le j} { dp[i - 1][k] } + |arr[i] - j|
由于 jj 的取值范围高至 10910^9,因此我们不妨考虑对原数组进行离散化,使得 jj 的含义变为原数组中第 jj 大的元素。记原数组中第 jj 大元素的值为 val[j]val[j],那么状态转移方程就变为:
dp[i][j]=min0kj{dp[i1][k]}+arr[i]val[j]dp[i][j] = \min\limits_{0 \le k \le j} { dp[i - 1][k] } + |arr[i] - val[j]|

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

优化思路一

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

完整参考代码

优化思路二

我们可以把 dp[i][j]dp[i][j] 的含义改为处理完前 ii 个元素并且 bijb_i \le j 时的最小操作数,那么相应地,状态转移方程式为:
dp[i][j]={dp[i1][j]=dp[i1][j]+arr[i]val[i]j=1min{dp[i1][j]+arr[i]val[i],dp[i][j1]}j>1dp[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[i1][j]+arr[i]val[i]dp[i - 1][j] + |arr[i] - val[i]| 代表 bi=jb_i = j 时的最小操作数,而 dp[i][j1]dp[i][j - 1] 则代表 bi<jb_i < j 时的最小操作数,两者中的最小值也就是 dp[i][j]dp[i][j] 啦。细节上为了方便可以把直接把 dp[0][j]dp[0][j] 全部初始化为 00。 这样做也可以省掉 kk 那一层循环使得复杂度降为 O(N2)\mathcal{O}(N^2)

完整参考代码

神奇的数学方法

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

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

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

fi(x)={minYX{arr[i]Y}i=1minYX{fi1(Y)+arr[i]Y}i>1f_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)opt(i) 代表使得 fi(x)f_i(x) 取值最小的 xx,换言之就是使得 arr[1i]arr[1 \dots i] 单调递增且操作次数最小时 arr[i]arr[i] 的取值。

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

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

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

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


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

我们发现:

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

整理一下:
fi(opt(i))={fi1(opt(i1))opt(i1)arr[i]fi1(opt(i1))+arr[i]opt(i1)opt(i1)>arr[i]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=1i = 1 的时候,显然 f1(opt(1))=0f_1(opt(1)) = 0。另外我们不难发现只有满足 arr[i]<opt(i1)arr[i] < opt(i - 1) 的阶段才会对最终的答案造成影响。也就是说:
fn(opt(n))=arr[i]<opt(i1), 2inarr[i]opt(i1)f_n(opt(n)) = \sum\limits_{arr[i] < opt(i - 1), \ 2 \le i \le n}|arr[i] - opt(i - 1)|

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

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

完整参考代码

This blog is under a CC BY-NC-SA 4.0 Unported License.
Link to this article: https://blog.codgician.pw/2018/05/08/codeforces-713c/