P12429 Sol || 这是个题吗

CarroT1212 · 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 也过了。应该是情况还可以继续进行一些非人力所可及的细分。