Description

现在我们有一个长度为 n 的整数序列 A。但是它太不好看了,于是我们希望把它变成一个单调严格上升的序列。但是不希望改变过多的数,也不希望改变的幅度太大。

求最少的改变数量,和在改变的数最少的情况下,每个数改变的绝对值之和的最小值。

Idea

首先一个套路。

要求严格单调的序列,就先将 $a_i-i$,对处理后的数列 $a’$ 做 $LIS$ 即可。

对于第二问,我们可以区间 $DP$。

枚举 $LIS$ 保留的相邻两个数 $i,j$,它们之间的数一定是前一半和 $a’_i$ 相等,后一半和 $a’_j$ 相等。因为数列随机生成,转移的数量远远到达不了 $\Theta(n^3)$。

Code