给个$n<=2000$长度数列，可以把每个数改为另一个数代价是两数之差的绝对值。求把它改为单调不增or不减序列最小代价。
话说这题其实是一个结论题。。找到结论应该就很好做了呢。
手玩的时候就有感觉，改造出来的数列的元素会不会全是原来数列里有的数？弄了几组发现没问题，但是还是踟蹰不前，不敢下手。。然后我就智障的换思路了。。。这个故事告诉我们发现一个暂时没找到反例的结论一定要大胆实践，反正交到OJ上不要钱。
所以这题结论就上面那个。具体证明呢。。我不会。。。
然后就简单了啊。有个很好想的状态$f[i][j]$第$i$位填数字$j$（因为$j$是只在原数组中出现的，所以可以离散化压缩状态为2000个）。于是每次枚举之，在上一位中找小于当前值的转移过来。
$f[i][j]=min(f[i-1][k]+|A[j]-a[i]|)$ $1<=k<=j$
然后k那一维做个前缀max减一维枚举就n方啦。
Upd:补证明。其实lyd书上是有的，但是并没看懂。后来由于thx学长帮助，大概理解了（%%%）。
数学归纳法。
对于$n=1$，显然成立。
对于$n=k-1$时假设其满足由原数列的数构成最优解。那么，考虑对于$n=k$。
当$A_n ≥ B_{n-1}$时（B为之后的数列）显然直接用$A_n$最优。
当$A_n ≤ B_{n-1}$时有两种选择。一种是由上一个$B_{n-1}$继续过来。
一种是把当前$B_i$向下调整。向下调整时，前面的构造好的数列要被迫下调。
那么假设下调至$x$。前面连着的一段应当也调为$x$。
（到这里都是lyd原话）
为什么统一调为$x$，前面构造好的数为什么不会变的比$x$更小从而更优？
如果之前的变得更小就更优的话，那我在之前就应当将它改为更小值保证最优了，而不是现在。
也就是说只能统一改为一个数$x$。
这时候用结论，这一段每个数与$x$差的绝对值要最小化，做多了就知道这是个中位数问题。
那么取这段数中的$mid$一定是可以保证代价最小的。
综上，$B_n$在保证最优的情况下只可能用A数列中有的数。
Upd2:见code下面。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define dbg(x) cerr<<#x<<" = "<<x<<endl
#define ddbg(x,y) cerr<<#x<<" = "<<x<<" "<<#y<<" = "<<y<<endl
using namespace std;
typedef long long ll;
template<typename T>inline char MIN(T&A,T B){return A>B?A=B,:;}
template<typename T>inline char MAX(T&A,T B){return A<B?A=B,:;}
template<typename T>inline T _min(T A,T B){return A<B?A:B;}
template<typename T>inline T _abs(T A){return A<?-A:A;}
template<typename T>inline T _max(T A,T B){return A>B?A:B;}
template<typename T>inline T read(T&x){
x=;int f=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;
while(isdigit(c))x=x*+(c&),c=getchar();return f?x=-x:x;
}
const int N=+;
ll f[N][N],ans;
int a[N],A[N],n,m;
inline void dp(){
for(register int i=;i<=n;++i){
ll minx=f[i-][];
for(register int j=;j<=m;++j)MIN(minx,f[i-][j]),f[i][j]=minx+_abs(A[j]-a[i]);
}
} int main(){//freopen("test.in","r",stdin);//freopen("test.out","w",stdout);
read(n);
for(register int i=;i<=n;++i)A[i]=read(a[i]);
sort(A+,A+n+),m=unique(A+,A+n+)-A-;
dp();
ans=f[n][];
for(register int i=;i<=m;++i)MIN(ans,f[n][i]);
reverse(a+,a+n+);
dp();
for(register int i=;i<=m;++i)MIN(ans,f[n][i]);
printf("%lld\n",ans);
return ;
}
Upd2
这题还有对应的拓展。（以及lyd付的思考题）
- 把原序列改为不严格单调增序列，至少改多少数？
- $ans=len-maxlen_{不下降子序列}$。原因很简单，保证有一个最长的不降序列，才能保证剩下的修改最少嘛。
- 把原序列改为严格单调增序列，至少改多少数？
- 令$B_i=A_i-i$。$ans=len-maxlen_{B的不下降子序列}$。这个比较重要。
- 首先要考虑的问题是，严格单调递增→若原数列中两数相差超过下标差时，这段数一定要改一些数，否则改掉也“挤不下”。这是问题所在。
- 要保证“挤得下”，就必须$A_j-A_i>=j-i $ $(i<j)$。即$A_j-j>=A_i-i$，才有严格递增。
- 更准确地说，要$A_i<A_{i+1}\Leftrightarrow A_i \leqslant A_{i+1}-1\Leftrightarrow A_i-i\leqslant A_{i+1}-(i+1)\Leftrightarrow B_i\leqslant B_{i+1}$
- 这是一个><号转≥≤的重要方法。所以要严格大于，我构造上述序列B，即可将其转化为大于等于。
- 两者是等价的。
- 方法是https://blog.csdn.net/guhaiteng/article/details/52549991的大佬的。tql%%%。
然后这题就可以顺带切掉了。
另外，将一开始问题的要求改为严格递增的最小代价，该怎么求？转化。同理，用上述方法构造序列。由于在原A序列和构造的B序列上修改代价是一样的，所以保证B满足不严格单调并且代价最小也就保证了A的严格单调。
然后相关题目是CF714E。
当然还有一个神仙的log做法。左偏树。我不会。逃。（要用log的做的题）