平滑数列

考虑判定答案是否可以不超过 $D$。

设保留原值的位置为 $i_1<i_2<\cdots<i_m$。如果相邻的两个保留位置为 $i<j$，则必须满足

$$|A_i-A_j| \le D(j-i).$$

这个条件也是充分的。当两个端点的差不超过 $D(j-i)$ 时，可以用整数填充它们之间被修改的位置，使每相邻一步的变化都不超过 $D$。开头和结尾处被修改的连续区间也总能填充。

因此，只需判断能否保留至少 $N-K$ 个原值。

子任务 4：$N\le2000$

设 $dp_i$ 表示以位置 $i$ 为最后一个保留位置时，最多能保留多少个原值。直接检查前面的哪些位置 $j<i$ 可以与 $i$ 一起保留，可得

$$dp_i=1+\max_{\substack{1\le j<i\\|A_i-A_j|\le D(i-j)}}dp_j.$$

如果没有满足条件的 $j$，则将最大值视为 $0$。

按 $i=1,2,\ldots,N$ 的顺序计算，并检查是否有 $\max_i dp_i\ge N-K$。一次判定需要 时间，结合二分查找后，时间复杂度为 ，空间复杂度为 。

对每个位置 $i$ 定义

$$X_i=A_i-Di,\qquad Y_i=A_i+Di.$$

对于 $i<j$，上述条件等价于

$$X_i\ge X_j,\qquad Y_i\le Y_j.$$

把点 $(X_i,Y_i)$ 按 $X_i$ 降序排序，若 相同则按 升序排序。设在这个顺序中， 的最长非递减子序列长度为 。那么 恰好等于能够同时保留的原序列元素的最大数量。

当 $D>0$ 时，因为 $Y_i-X_i=2Di$，满足两个坐标不等式的点的顺序也与原下标顺序一致。当 时，；在按 降序排序后，一个非递减子序列只有在数值相等时才能同时包含多个点，因此结论仍然成立。

所以，当且仅当 $L\ge N-K$ 时，$D$ 可行。使用 upper_bound 可以在 $O(N\log N)$ 时间内求出最长非递减子序列。

可行性关于 $D$ 单调，因此在 $0$ 到原序列最大相邻差之间二分答案。总时间复杂度为 $O(N\log N\log C)$，其中 $C\le 2\cdot 10^9$；空间复杂度为 。

Solution written by GPT6