自动搬运

查看原文

来自洛谷，原作者为

	CarroT1212 chrono::system_clock::now().time_since_epoch().count()

搬运于2025-08-24 23:15:31，当前版本为作者最后更新于2025-05-10 20:27:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

最终的 $b$ 形态一定是所有极长的相等段上下交替。朴素的 DP 是 $dp_{i,j,0/1}$ 表示前 $i$ 个处理完，$b_i=j$，当前的 $b_i$ 相等段为下/上时的最小代价。

容易转移：$dp_{i,j,0}=\min(\min\limits_{k>j}\{dp_{i-1,k,1}\},dp_{i-1,j,0})+|a_i-j|$，$dp_{i,j,1}=\min(\min\limits_{k<j}\{dp_{i-1,k,0}\},dp_{i-1,j,1})+|a_i-j|$。

光是状态数就爆炸了，显然需要从 DP 性质入手。

有聪明的选手猜了一下 $j$ 只可能取某个 $a_x$，没拿到什么分。

有更聪明的选手猜了一下 $j$ 只可能取某个 $a_x-1,a_x,a_x+1$，获得了 $O(n^2)$ 的分。

有非常聪明的选手猜了一下 $j$ 只可能取某个 $[i-O(1),i+O(1)]$ 内的 $x$ 的 $a_x-1,a_x,a_x+1$，获得了满分。

我估计一个合理的猜测思路是，手玩感觉取到 $a_x-2,a_x+2$ 没什么含义，然后做 $a_i<a_{i+1}$ 的分发现长度超过 $2$ 的连续段一定可以被替换成其它情况，于是就猜到了。

下证：DP 中每个 $i$ 只保留 $j$ 为 $x\in[i-4,i+4]$ 的 $a_x-1,a_x,a_x+1$ 的情况不影响答案正确性。证明大部分参考自官方题解，一些图示可以对着官方题解看一看，这里就不贴了。

考虑最终的 $b$ 形态。

如果 $[l,r]$ 满足其中没有任何 $i$ 使 $a_i=b_i$，则称其为坏区间；称 $b_i$ 中，大于两侧值的一段极长的相等区间 $[l,r]$ 为峰，小于两侧为谷。称峰/谷的高度为对应的 $b_i$ 值。

一定存在一个代价最优的 $b$ 满足：

• 性质 1. 峰 $[l,r]$ 内没有任何一个 $l<i<r$（即不在峰两端）的 $a_i$，小于这段峰的高度。
  • 这样的 $b_i$ 单开一个谷的代价显然是更小的。
• 性质 2. 峰 $[l,r]$ 内满足 $l<l'\le r'<r$ 的的坏区间 $[l',r']$，长度至多为 $3$。
  • 根据性质 1，设 $[l',r']$ 里的 $b_i$ 均大于峰的高度。假设存在坏区间 $[l',r']$ 长度至少为 $4$。不妨只考虑 $=4$ 的情况。
  • 设 $x$ 为峰高，$y=\min(a_{l'+1},a_{r'-1})$。把 $[l',r']$ 的 $b_i$ 取值改为 $x-1,y,y,x-1$，那么 $[l',r']$ 不再是坏区间，而代价不劣。
• 性质 3. 峰 $[l,r]$ 内满足 $l=l'\le r'<r$ 的的坏区间 $[l',r']$，长度至多为 $3$。
  • 类似性质 2。可以把 $[l',r']$ 内的 $b_i$ 改为 $y,y,y,x-1$。
• 由性质 3 同理可证峰内 $l<l'\le r'=r$ 的坏区间 $[l',r']$ 长度至多为 $3$。
• 性质 4. 整个峰 $[l,r]$ 为坏区间，当且仅当（建议先看证明）$l=r\wedge a_l<b_l\wedge (b_{l-1}+1=b_l\vee b_{l+1}+1=b_l)$。
  • 考虑一个坏峰。设其中大于峰高的 $a_i$ 个数为 $high$，小于峰高的 $a_i$ 个数为 $low$。
  • 如果 $high\ge low$，这时可以把峰高提升到 $[l+1,r-1]$ 内 $a_i$ 的最小值，峰不再是坏区间，且代价一定不劣。由性质 1 得 $low\le 2$，所以 $[l,r]$ 长度 $\ge 4$ 时一定 $high\ge low$。
  • 否则 $high<low$，这时 $[l,r]$ 长度最多为 $3$。峰高整体变化的话需要降低才不会让代价增加。
    • 如果峰高可以无障碍降低到 $\max(a_l,a_r)$，那么也没问题。
    • 可如果降低的过程中出现了 $b_{l-1}+1=b_l$ 或者 $b_{r+1}+1=b_r$，那再整体降低一步这个峰就不存在了。这不是我们想要的。
    • 但是由于一定有 $a_l<b_l$ 且 $a_r<b_r$，我们可以缩短这个峰的长度。具体来说，如果 $b_{l-1}+1=b_l$，则 $a_l\le b_{l-1}=b_l-1$，于是可以让 $[l,r]$ 左侧的谷往右扩张一位（$l=1$ 就新建一个谷）。容易发现这并不影响谷的合法性，同时还把峰转化为了 $high\ge low$ 的情况。$b_{r-1}+1=b_r$ 同理。
    • 所以一个峰无法这样调整为非坏区间的条件，就是上面说的了。
• 同理，谷也有类似的以上几条性质。
• 性质 5. $b_l=b_{l+1}+1$ 时，若 $[l,l]$ 为峰，$[l+1,l+1]$ 为谷，则它们不能同时是坏的。
  • 若它们都是坏的，有 $a_l<b_l$ 且 $a_{l+1}>b_{l+1}$。
  • 如果 $a_l>b_{l-1}$，直接把 $b_l,b_{l+1}$ 同时降低 $b_l-a_l$ 即可。
  • 否则，把 $b_l,b_{l+1}$ 都改为 $b_{l-1}$。
• 由性质 5 可以推出一个坏峰两端不可能都是坏谷，坏谷两端也不可能都是坏峰。
• 根据前面的所有性质，坏区间最长最极限的情况是：一个长度 $\ge 4$ 的谷的后三位 + 坏峰 + 坏谷 + 一个长度 $\ge 4$ 的峰的前三位。峰谷可互换。
• 那么这时这个坏区间里的所有 $i$，一定都满足 $b_i$ 等于 $[i-4,i+4]$ 范围内的某个 $a_x-1,a_x,a_x+1$。得证。

相信有了这个结论之后你是知道怎么写代码的。

哎其实感觉证明还是比较有意思的，只是这种结论出现在 OI 题里区分度就成玄学了，不过 BOI 场上好像也没几个人想到这东西。

但有人把这个阈值取 $2$ 也过了。应该是情况还可以继续进行一些非人力所可及的细分。