1944: 吃面包
题目描述
yk最近比较兴奋，因为有数学保送啦~ 如果noip2010他再拿一个保送的话，那么yk就拿了四个保送了！！（orz…）yk兴奋到梦里都在跳…
yk梦到自己来到N个面包做成的城堡前面（为什么是面包？？？因为yk喜欢吃面包呗…（yk注：其实yk不喜欢吃面包L）），这N个面包城堡从左向右排成一列，每个面包城堡一个初始的高度，从左往右数第i个城堡的高度为A[i]。现在yk要从第1个跳到第N个城堡，但是yk比较懒，他只想不停地向上跳或者向下跳（平着跳也可以），但是不想一会儿向上跳，一会儿向下跳，否则yk的好心情会被破坏，所以他请jzj过来帮他吃掉一些面包或者盖上一些面包（可怜的jzj……），也就是让某些城堡的高度增加或者减少，以此满足yk快乐地跳城堡的心愿。
对于每一个面包城堡，jzj吃掉x个单位长度和盖上x个单位长度所耗费的力气都是x，jzj想花尽量少的力气帮yk完成心愿。也就是对于原来面包城堡高度为A_1，A_2，A_3…A_N，jzj通过耗费力气将面包城堡高度变为B_1,B_2,B_3…B_N，现在想在B数组不降或不升的前提下，|A_1 - B_1| + |A_2 - B_2| + ... + |A_N - B_N|最小。
输入
第1行: 输入1个整数：N
第2..N+1行: 第i+1行为1个整数：A_I
输出
第1行: 输出1个正整数，表示jzj为了帮助yk完成心愿所需要花费的最小力气。
样例输入 复制
7
1
3
2
4
5
3
9
样例输出 复制
3提示
【样例解释】：
jzj将第一个高度为3的城堡的吃掉一口变为2，将第二个高度为3的城堡盖上两层增加到5，花费的力气和为|2-3|+|5-3| = 3，并且每个城堡的高度为一个不下降序列1,2,2,4,5,5,9。
【数据规模】
100% N<=2000，0 <= A_i <= 1,000,000,000