解题思路：我们需要对单调不下降和单调不上升的情况分别求出解，然后求一个最小值就好了。本题的关键在于找到该问题的一个性质：一定存在一组最优解b[i]，使得每个b[i]都是原序列中a[i]的值。
以下证明来自yxc大佬
证明：（这里是那不下降的情况来举例）
假设某个最优解如下图所示，其中 {Ai}是原序列，{A′i}?是将原序列排序后的序列，图中红色圆圈表示每个 Bi。
考虑每个位于 A′i,A′i+1之间的一段 Bi，比如上图中粉色框中的部分。
则我们在 {Ai} 中粉色框对应的这段里统计出大于等于 A′i+1?的数的个数 x，小于等于 A′i?的数的个数 y，那么：
（这里详细解释下x和y表示的意思，当Ai>=A'i,x++,当Ai<=A'i,y++)
如果 x>y，将粉色框中的 Bi?整体上移，使最高的一个圆圈达到上边界，结果会变好；
如果 x<y，将粉色框中的 Bi?整体下移，使最低的一个圆圈达到下边界，结果会变好；
如果 x=y，则上面两种方式均可，结果不会变差；
综上所述，只要存在某个 BiBi 的值不在原序列中，我们一定可以将它调整成原序列中的值，且结果不会变差。
证毕。
下面就是用DP求解的过程了，状态表示：f[i][j]表示已经为A[1~i]构造了对应的B[i]，且最后一个B[i]=A‘[j]的集合，而这里是让我们求一个最小值
状态计算：f[i][j]可以由那些状态转移过来？我们只考虑最后一步的上一步，最后一步我们是选择了A’[j]作为B[i]，那它的上一步就是选择B[i-1]，B[i-1]的取值范围可以是A'[1~j],从中选择一个代价最小的minv,加上当前B[i-1]选择的代价构成f[i][j],即f[i][j]=minv+abs(A'[j]-A[i])，minv是我们每次遍历j的时候顺便更新的，这样就节省了一层循环。
上代码：
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=2010;
int a[N],b[N];
int f[N][N];
int n;
int dp()
{
for(int i=1;i<=n;i++)
b[i]=a[i];
sort(b+1,b+n+1);
for(int i=1;i<=n;i++)
{
int minv=0x3f3f3f3f;
for(int j=1;j<=n;j++)
{
minv=min(minv,f[i-1][j]);
f[i][j]=minv+abs(b[j]-a[i]);
}
}
int res=0x3f3f3f3f;
for(int i=1;i<=n;i++)
res=min(res,f[n][i]);
return res;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
int ans=dp();
reverse(a+1,a+n+1);
ans=min(ans,dp());
cout<<ans<<endl;
return 0;
}
