n个数,每个数可以任意+1,-1

(1 min to read)

变成非降序列的最小代价

显然对于第i个数如果要变就变成之前已经出现过的数,所以离散化后dp即可,$O(n^2)$考虑当前数y,以及之前的最大值x,如果$y\lt x$,此时需要将x变小,y变大,容易发现不管怎么调整代价都是$y-x$,这边的策略是直接把y变成x。考虑y之前的最大值z,如果$z\leq x$,显然没有问题,否则我们也不用关心改成了什么,因为现在最大值变成了z,那就尽可能减小所以用一个大根堆,如果当前数小于堆顶,就把堆顶变成当前数

变成严格降序列

对每个数减去下标后,套用上面的做法,一个小trick