P83116

平整道路

难度 5 级 初三 动态规划 线性
讨论 统计 1通过 3提交 33.3%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

一条笔直的土路连接着FJ农场的两块田地,但它的海拔变化比FJ想要的要大。他的奶牛不介意爬上或爬下一个斜坡,但它们不喜欢交替的丘陵和山谷。FJ希望添加和清除道路上的污垢,使其成为一个单调的斜坡(向上或向下倾斜)。

给定N个整数A_1,...,A_N(1≤N≤2000)描述了沿道路N个等距位置的海拔高度(0≤A_i≤1000000000),从第一个场地开始,到另一个场地结束。FJ希望将这些海拔调整到新的序列B_1、…、…、,B_N要么不增加,要么不减少。由于在道路沿线的任何位置添加或清除污垢的成本相同,因此改造道路的总成本为|A_1-B_1|+|A_2-B_2|+…+|A_N-B_N|

请计算平整道路的最小成本,使其成为一个连续的斜坡。

输入

第一行一个整数 N

后面N行,每行一个整数,表示道路的海拔

输出

最少的成本

样例

样例 1
输入
7
1
3
2
4
5
3
9
输出
3

来源

USACO

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交