题目链接：
题目描述：
给出一组数，每个数代表当前位置的地面高度，问把路径修成非递增或者非递减，需要花费的最小代价？
解题思路：
对于修好的路径的每个位置的高度肯定都是以前存在的高度，修好路后不会出现以前没有出现过得高度
dp[i][j]代表位置i的地面高度为第j个高度，然后我们可以把以前的路修好后变成非递减路径，或者把以前的路径首尾颠倒，然后修成非递减路径。状态转移方程为：dp[i][j] = min(dp[i-1][k]) + a[i] - a[j]；因为要把路径修成非递减路径，所以a[j]>a[k]，所以我们要三重循环来搞，时间复杂度O(n^3)。如果我们对原来数列进行复制排序的话，a[j]>a[k]就转化为了j>k,这样就成功的把时间复杂度从O(n^3)降为O(n^2)。空间复杂度也可以用滚动数组从O(n^2)变为O(n)。
注意啦！注意啦！一定要用长整形，要不然会爆炸。用了长整形的话，取绝对值的时候就不能用abs了，只有手动实现或者用fabs咯。亲试······ce好几次(吐血~)
#include<stdio.h>
#include <queue>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<algorithm> using namespace std;
typedef long long LL;
const LL maxn = ;
const LL INF = 0xfffffff;
LL dp[maxn][maxn];
//dp[i][j]第i个木棒，长度是j LL solve (LL a[], LL b[], LL n)
{
for (int i=; i<=n; i++)
dp[][i] = fabs (b[i] - a[]);
for (int i=; i<=n; i++)//第i个位置
{
LL Min = dp[i-][];
for (int j=; j<=n; j++)
{
Min = min (dp[i-][j], Min);
dp[i][j] = Min + fabs(a[i] - b[j]); }
}
LL Max = dp[n][];
for (int i=; i<=n; i++)
Max = min (Max, dp[n][i]);
return Max;
} int main ()
{
LL n, a[maxn], b[maxn];
while (scanf ("%lld", &n) != EOF)
{
for (int i=; i<=n; i++)
{
scanf ("%lld", &a[i]);
b[i] = a[i];
}
sort (b+, b+n+); LL ans = solve (a, b, n);
for (int i=, j=n; i<j; i++, j--)
swap (a[i], a[j]); ans = min (ans, solve(a, b, n));
printf ("%lld\n", ans);
}
return ;
}