题解 P2501 【[HAOI2006]数字序列】

· · 题解

本题解由ydc神犇编写，因为原文为pdf，在此做个搬运。

1.前言

四月二十多号做的这道题了，当时正好是省选完挂，非常难过、心情沉重的刷着 bzoj 上第一版的题。在惊呼 HAOI 的水题堆后，迎来了这么一道在当时的我看来是个结论题的题，然后没怎么细想的就用结论过了这个题

今天苏雨翔找我问……我发现不记得了，于是翻以前的题解，终于搞懂了

2.第一问

直接做不好做，考虑补集转化，最大化不修改的点最多

假设 a 是原数组，对于 i, j, i < j 使得 i, j 不被修改的必要条件是 a_j - a_i \ge j - i, 这样就能通过把中间 j - i - 1 个数修改让他们严格递增，反之无解

于是一个 dp 方程跃然纸上，

f(i) = max_{j=1}^{i-1} f(j)+1(a_i-a_j \ge i-j) a_j-a_i \ge j-1 \Rightarrow a_j-j \ge a_i-i$，定义$b_i = a_i-i$，于是$b_j\ge b_i

构造出b数组后，就成了求b的最长不下降子序列

第一问的答案就是n-b的最长不降子序列

3.第二问

题意要求，在满足第一问的前提下，要让变化的幅度最小

对于第一问，如果 j 能转移到 i，则有 f(j) + 1 = f(i)，进行挂链后，假设g(i) 表示 1 ~ i 的答案，有

g(i) = min_{f(j)+1=f(i)} g(j)+w(j+1,i) 让 $a$ 数组单调递增，等价于让 $b$ 数组单调不降，考虑让 $b$ 数组单调不降的最小花费 由于有 $f(j) + 1 = f(i)$，所以 $\forall j < k < i, b_k \le b_j$ 或者 $b_i \le b_k$, 现在一个结论是， $w(j, i)$ 的方案，一定会以某个 $k$ 为分界使得 $[j,k]$ 均为 $b_j$ 且 $[k+1,i]$ 均为 $a_i

试着证明一下

使用数学归纳法。

一两个数显然成立。

假设 k 个数，以下标为横坐标，最优方案下的 b 值为纵坐标，按照那个结

论分布好了，很像是一上一下两条水平线，左边一段在下面那根，右边一段在上面那根，现在冒出一个奇葩点 p，他在两个水平线之间

显然他的 a 值在上面的上方或下面的下方，接下来就是一堆分情况讨论的事情而已。首先他不能做在上面点和在下面点的临界点，不然的话他往上走或往下走总能找到更好地。也就是说，他现在要么夹在一坨在下方的点中间在他们上方，要么在一坨在上边界的点中间却在下方

两种情况很类似，讨论第一种即可。那么他一定会导致他右边这些在下方的点为了满足合法性不得不飞到他上面，由于这个点不在的时候是优方案，所以我们知道这右下方几个点往上跑 1 格会使变大。

既然这样的话，如果这个讨厌的点往下走会使花费变少，他肯定要往下走。

否则的话，就说明他往下走 x 格要增加 x 的花费。但是人多力量打，他走一格才一的花费，敌不过后面一坨点

其实这样算的话也是不全面的，因为后面这些点有可能随他乱动代价都一样，这时候大家都往上跑走到最最上面，花费还是变少了

于是皆大欢喜