题目描述 Description
Mr. Ling打算好好修一下学校门口的那条凹凸不平的路。按照Mr. Ling的设想，修好后的路面高度应当单调上升或单调下降，也就是说，高度上升与高度下降的路段不能同时出现在修好的路中。
整条路被分成了N段，N个整数A_1，…，A_N依次描述了每一段路的高度。Mr.Ling希望找到一个恰好含N个元素的不上升或不下降序列B_1，...，B_N，作为修过的路中每个路段的高度。由于将每一段路垫高或挖低一个单位的花费相同，修路的总支出可以表示为：
|A_1 - B_1| + |A_2 - B_2| + ... + |A_N - B_N|
请你计算一下，Mr. Ling在这项工程上的最小支出是多少。Mr. Ling向你保证，这个支出不会超过2^31-1。
输入描述 Input Description
第1行：输入1个整数N；
第2..N+1行：第i+1行为i个整数A_i
输出描述 Output Description
第1行：输出1个正整数，表示把路修成高度不上升或高度不下降的最小花费。
样例输入 Sample Input
7
1
3
2
4
5
3
9
样例输出 Sample Output
3
数据范围及提示 Data Size & Hint
【样例说明】
将第一个高度为3的路段的高度减少为2，将第二个高度为3的路段的高度增加到5，总花费为|2-3|+|5-3| = 3，并且各路段的高度为一个不下降序列1，2，2，4，5，5，9。
【数据范围】
30%的数据：1< N≤50，0≤ A_i ≤1,000；
100%的数据：1≤ N≤2000，0≤ A_i ≤1,000,000,000。
/*
修改次数不会达到n，修改的数值一定是原先存在的
*/
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std;
const int maxn = ;
const ll inf = 98765432101234LL;
struct orz{
ll p;
ll v;
};
bool cmp(orz a,orz b){
return a.v < b.v;
}
ll n,k,a[maxn],dp[maxn][maxn],dp2[maxn][maxn],ans;
orz b[maxn];
inline ll read(){
char ch=getchar();
ll f=,x=;
while(!(ch>=''&&ch<='')){if(ch=='-')f=-;ch=getchar();};
while(ch>=''&&ch<=''){x=x*+(ch-'');ch=getchar();};
return x*f;
} int main(){
n = read();
for(int i = ;i <= n;i++){
a[i] = b[i].v = read();
b[i].p = i;
}
sort(b+,b++n,cmp);
for(int i = ;i <= n;i++){
for(int j = ;j <= n;j++){
dp[i][j] = dp2[i][j] = inf;
}
}
for(int i = ;i <= n;i++){
for(int j = ;j <= n;j++){
dp[i][j] = min(dp[i][j],dp[i][j-]);
dp[i][j] = min(dp[i][j],dp[i-][j]+abs(b[j].v-a[i]));
}
}
for(int i = n;i >= ;i--){
for(int j = ;j <= n;j++){
dp2[i][j] = min(dp2[i][j],dp2[i][j-]);
dp2[i][j] = min(dp2[i][j],dp2[i+][j]+abs(b[j].v-a[i]));
}
}
cout<<min(dp[n][n],dp2[][n])<<endl;
return ;
}