严格递增改造 题解

思路

令 $b_i=a_i-i$，修改后的数组严格递增，等价于修改后的 $b$ 非递减。目标变成最小化 $\sum|b_i-c_i|$，其中 $c$ 非递减。

最优 $c_i$ 一定可以取自原数组 $b$ 的某个值。将所有 $b_i$ 排序去重为 $v_1<\cdots<v_m$，即可在这些候选值上动态规划。

做法

子任务 1 枚举小值域内的所有严格递增目标数组并直接计算代价。

子任务 2 设 $dp_{i,j}$ 表示前 $i$ 项且 $c_i=v_j$ 的最小代价，直接枚举前一项候选 $k\le j$，复杂度 $O(nm^2)$。

满分算法维护前一行的前缀最小值：

这样每层只需线性扫描全部候选值。

正确性证明

减去下标把“严格递增”与“非递减”一一对应且不改变每项修改代价。对固定相邻候选区间，若某个 $c_i$ 不等于任一输入 $b$ 值，将其移动到最近端点不会破坏非递减性，也不会增大绝对值和，因此只需考虑候选集合。动态规划枚举了所有非递减候选序列，并对每个末值取最小代价，所以所得答案最优。

复杂度

满分算法时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。