首先来看一下蓝书上面的两个思考题
一.
将一个序列\(A\)改成单调不下降序列，最少需要修改多少个数？
答：用\(A\)的长度减去其最长单调不下降子序列的长度即可
那如果在最少修改数的基础上，我要让每个数改变的绝对值之和的最小值最小怎么办？
首先，这根“Making the Grade”这道题目很像，所以我们考虑用DP
我们假设已经选好了一个\(A\)的最长单调不下降子序列作为其保留的数，然后把剩下的数进行修改
由“分级”这一道题目给我们带来的启发，我们可以想到一个引理：设\(a[i]\)和\(a[j]\)是我们选出的\(A\)的最长单调不下降子序列中相邻的两个数（在原序列\(A\)中不一定相邻），那么我们修改\(a[i]\)和\(a[j]\)中间的数时，可以找到一个分界点\(k\)，让\(a[i+1\)~\(k]\)的值全部修改为\(a[i]\) ， \(a[k+1\)~\(j]\)的值全部修改为\(a[j]\)
这个证明与AcWing上y总的证明以及我的写在博客里面的证明非常像：我们假设已经随便移动这些数
