前言
听说最早的题目原型是CF13C
下面按这题来讲，其实就是换成了不降。
朴素DP
定义$f_i(X)$ 为前$i$个数变为不降序列且$a_i\le X$的最小步数。
显然有
$f_1(X) = min_{Y\le X}{|a_1-Y|}$
$f_i(X) = min_{Y\le X}{f_{i-1}(Y)+|a_i-Y|}$
离散的DP
可以令${b_i}$为${a_i}$的一个有序copy，复杂度$O(n^2)$。
详情请阅 CF13C Tutorial 。
单调性优化
$f_i(X) = min_{Y\le X}{f_{i-1}(Y)+|a_i-Y|}=min(f_i(X-1),f_{i-1}(X)+|a_i-X|)$
由绝对值和最小值的性质，$f_i$对于$X$是一个单减的非负函数，并最后保持一个非负值。
考虑其“斜率函数” $g_i(X)=f_i(X+1)-f_i(X)$，则$g_i(X)$单增（不会证）。
$g_i(X)$的值域为有限个小于等于0的整数，我们将值域中每个数对应的最小的$x$写为一个序列（即“变化点”），即序列的最后一个数为使得$g_i(x)=0$的最小的$x$，……
突然发现我还是不会证，，那就没必要了，，大家还是看资料吧。。
