题目描述 Description
Petya是一个非常好玩孩子。他很无聊，因此他开始玩下面的游戏：
他得到一个长度为N的整数序列，他会对这些数字进行操作，他可以把某个数的数值加1或者减1(当然他可以对同一个数操作很多次)。他的目的是使得数列非递减，即在修改之后，数列满足a1≤a2≤...≤aN 。
请你告诉他，他最少要操作多少次。
输入描述 Input Description
第1行一个整数n。
第2行n个整数 a1、a2、……、an，每两个整数之间用一个空格隔开
输出描述 Output Description
输出只有一行1个整数，表示最少的操作次数。
样例输入 Sample Input
5
3 2 -1 2 11
样例输出 Sample Output
4
数据范围及提示 Data Size & Hint
对于30%的数据 1≤n≤60 的绝对值不超过
对于 60%的数据 1≤n≤200
对于100%的数据1≤n≤5000 的绝对值不超过。
/*
同修路
*/
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll int
using namespace std;
const int maxn = ;
const ll inf = ~0U>>;
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],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] = 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]));
}
}
cout<<dp[n][n]<<endl;
return ;
}