• [1677] 没钱了

  • 时间限制: 1000 ms 内存限制: 655350 K
  • 问题描述
  • Gealo从家到学校总共要经过n条路,但是他嫌弃这些路高低不平于是他决定花点钱修一下路
    给出N个整数A1,...,AN(1≤N≤2000),描述沿着道路的每个N个等间距位置处的高程(0≤A≤1,000,000,000),从第一场开始并以其他。 Gealo想将这些高程调整到一个新的序列B1。 ...,BN是单调递增的。由于在道路上的任何位置增加或清除污物费用相同的金额,修改道路的总成本是
    | A 1 - B 1 | + | A 2 - B 2 | + ... + | AN - BN |
    Gealo并不是有钱人于是想尽可能的省钱。问最少的成本是多少
  • 输入
  • 输入t,(1<=t<=15)表示组数。
    每组一个输入一个n(1<=n<=3000)表示一共路的个数
    下一行输入n个数ai(1<=ai<=1e9)
  • 输出
  • 输出一个数表示最小的成本
  • 样例输入
  • 1
    7
    2 1 5 11 5 9 11
  • 样例输出
  • 9
  • 提示
  • 来源
  • 本站或者转载
  • 操作

显示春菜