1592: [Usaco2008 Feb]Making the Grade 路面修整

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 428 Solved: 316
[Submit][Status][Discuss]

Description

FJ打算好好修一下农场中某条凹凸不平的土路。按奶牛们的要求，修好后的路面高度应当单调上升或单调下降，也就是说，高度上升与高度下降的路段不能同时出现在修好的路中。整条路被分成了N段，N个整数A_1, ... , A_N (1 <= N <= 2,000)依次描述了每一段路的高度(0 <= A_i <= 1,000,000,000)。FJ希望找到一个恰好含N个元素的不上升或不下降序列B_1, ... , B_N，作为修过的路中每个路段的高度。由于将每一段路垫高或挖低一个单位的花费相同，修路的总支出可以表示为： |A_1 - B_1| + |A_2 - B_2| + ... + |A_N - B_N| 请你计算一下，FJ在这项工程上的最小支出是多少。FJ向你保证，这个支出不会超过2^31-1。

Input

* 第1行: 输入1个整数：N * 第2..N+1行: 第i+1行为1个整数：A_i

Output

* 第1行: 输出1个正整数，表示FJ把路修成高度不上升或高度不下降的最小花费

Sample Input

7
1
3
2
4
5
3
9

Sample Output

HINT

FJ将第一个高度为3的路段的高度减少为2，将第二个高度为3的路段的高度增加到5，总花费为|2-3|+|5-3| = 3，并且各路段的高度为一个不下降序列 1,2,2,4,5,5,9。

Source

Gold

题解：其实。。。就是将原来的数列改成排序后的样子需要多少的改动。。。

所以公式很明显\( F\left[ i,j \right]=min\left(F\left[ i-1 ,k \right] + \left|b_i-a_i \right| \right) (1\leq k\leq j) \)

 /**************************************************************

     Problem:

     User: HansBug

     Language: Pascal

     Result: Accepted

     Time: ms

     Memory: kb

 ****************************************************************/

 type arr=array[..] of longint;

 var

    i,j,k,l,m,n,ans:longint;

    a,d:arr;

    b,c:array[..,..] of longint;

 function min(x,y:longint):longint;

          begin

               if x<y then min:=x else min:=y;

          end;

 procedure deal;

           begin

                for i:= to n do

                    for j:= to n do

                        begin

                             b[i,j]:=c[i-,j]+abs(a[i]-d[j]);

                             if j= then

                                c[i,j]:=b[i,j]

                             else

                                 c[i,j]:=min(b[i,j],c[i,j-]);

                        end;

                for i:= to n do ans:=min(ans,b[n,i]);

           end;

 procedure swap(var x,y:longint);

           var z:longint;

           begin

                z:=x;x:=y;y:=z;

           end;

 procedure sort(l,r:longint;var a:arr);

           var i,j,x,y:longint;

           begin

                i:=l;j:=r;x:=a[(l+r) div ];

                repeat

                      while a[i]<x do inc(i);

                      while a[j]>x do dec(j);

                      if i<=j then

                         begin

                              swap(a[i],a[j]);

                              inc(i);dec(j);

                         end;

                until i>j;

                if i<r then sort(i,r,a);

                if l<j then sort(l,j,a);

           end;

 begin

      readln(n);

      ans:=maxlongint;

      for i:= to n do

          begin

               readln(a[i]);

               d[i]:=a[i];

          end;

      sort(,n,d);

      deal;

      for i:= to n div  do swap(d[i],d[n-i+]);

      deal;

      writeln(ans);

      readln;

 end.

巴特西

1592: [Usaco2008 Feb]Making the Grade 路面修整