题意： 给定一个长度为N的数组，我们可以对其中的数进行修改，每次修改有一个代价，对于一个数x，修改成y之后的代价就是abs（x-y）。
现在我们要将这个数列变成一个单调不减的，问所需要的代价。
其中N<=5000,-10^9=<a[i]<=10^9
解决
solution 1
看到这个题目，很容易就想到了DP，然后有了一个非常暴力的方程。
用f[i][j]代表前i个数，最后一个数的高度为j所需要的最少代价。
很容易写出方程f[i][j]=Min(f[i-1][k]+abs(j-k))
这个方程时间复杂度为O（N*max*max）,其中max是最大的a[i]，当然，对于负数的情况可以将整个数组向上平移变成正数。
可以看到的是，这个方程的时间复杂度实在太高了，在空间上也难以承受。所以我们只能另寻他法。
solution 2
有了上面的基础，很快有了优化的办法，那就是离散化！
既然总的数据量只有5000，那么我们可以把每个数在数列中的rank作为这个数的大小
那么得到f[i][j]代表前i个数，最后一个数为数列中第j大的数的代价。
方程可以写出f[i][j]=Min(f[i-1][k]+abs(b[j]-a[i]))，其中b[j]就是第j大数的大小。
时间复杂度o（N^3），还是不能很好的解决问题,所以我们还要寻求其他的办法。
solution 3
然后我开始想这样一个问题，如果说f[i][j]要大于f[i][j-1],那么计算这样的f[i][j]还有什么意义呢？
因为我第i个数得到的大小为b[j-1]的消耗要比得到b[j]的消耗少，（b数列是单增的），那么在i+1个数的决策的时候，这样的
f[i][j]还有什么意义呢？！(大家可以自己证明一下)
所以我们必须还要压缩状态！
修改我们的方程，用f[i][j],代表前i个数，第i个数小于等于b[j]的最小花费
方程可以写成f[i][j]=Min(f[i][j-1],f[i-1][j]+abs(a[i]-b[j]))
然后由于转移只是用到了相邻状态，可以用滚动数组来优化空间
即 f[i]=Min(f[i-1],f[i]+abs(a[i]-b[j]))
时间复杂度 O（N^2），空间复杂度O（N）
这个问题还有更优秀的算法，在此不再做过多讲解，这里已经能很好的解决这个问题，我们可以看到整个思维的过程其实是循序渐进的。
题目第一次由于对数的大小估计不足最终RE了，一定要使用long long
这里是本人的最终代码，大神们不要BS
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <math.h>
4 #define N 5050
5 long long dp[ N ] , a [ N ] , b [ N ] ,ans ;
6 int cmp (const void * a , const void * b )
7 {
8 return *(int *) a - * ( int * ) b ;
9 }
10 long long Min(long long x, long long y)
11 {
12 return x>y?y:x;
13 }
14 int main ( void )
15 {
16 int i , n , j ;
17 scanf("%d",&n);
18 for ( i = 1 ; i <= n ; i++ )
19 {
20 scanf( "%d" , & a [ i ] ) ;
21 b[i]=a[i];
22 }
23 qsort (b+1,n,sizeof(b[0]),cmp);
24
25 for ( i = 1 ; i <= n ; i++ )
26 for ( j = 1 ; j <= n ; j++ )
27 {
28 dp[j]+=abs(b[j]-a[i]);
29 if (j>1)
30 dp[j]=Min(dp[j],dp[j-1]);
31 }
32 ans = dp[1] ;
33 for (i=2;i<=n;i++)
34 if (dp[i]<ans)
35 ans=dp[i];
36 printf("%I64d\n",ans);
37 return 0 ;
38 }