Poj 3666 Making the Grade (排序+dp)

题目链接:

  Poj 3666 Making the Grade

题目描述:

  给出一组数,每个数代表当前位置的地面高度,问把路径修成非递增或者非递减,需要花费的最小代价?

解题思路:

  对于修好的路径的每个位置的高度肯定都是以前存在的高度,修好路后不会出现以前没有出现过得高度

  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好几次(吐血~)

 1 #include<stdio.h>
 2 #include <queue>
 3 #include<string.h>
 4 #include<math.h>
 5 #include<stdlib.h>
 6 #include<algorithm>
 7 
 8 using namespace std;
 9 typedef long long LL;
10 const LL maxn = 2010;
11 const LL INF = 0xfffffff;
12 LL dp[maxn][maxn];
13 //dp[i][j]第i个木棒,长度是j
14 
15 LL solve (LL a[], LL b[], LL n)
16 {
17     for (int i=1; i<=n; i++)
18         dp[1][i] = fabs (b[i] - a[1]);
19     for (int i=2; i<=n; i++)//第i个位置
20     {
21         LL Min = dp[i-1][1];
22         for (int j=1; j<=n; j++)
23         {
24             Min = min (dp[i-1][j], Min);
25             dp[i][j] = Min + fabs(a[i] - b[j]);
26 
27         }
28     }
29     LL Max = dp[n][1];
30     for (int i=1; i<=n; i++)
31         Max = min (Max, dp[n][i]);
32     return Max;
33 }
34 
35 int main ()
36 {
37     LL n, a[maxn], b[maxn];
38     while (scanf ("%lld", &n) != EOF)
39     {
40         for (int i=1; i<=n; i++)
41         {
42             scanf ("%lld", &a[i]);
43             b[i] = a[i];
44         }
45         sort (b+1, b+n+1);
46 
47         LL ans = solve (a, b, n);
48         for (int i=1, j=n; i<j; i++, j--)
49             swap (a[i], a[j]);
50 
51         ans = min (ans, solve(a, b, n));
52         printf ("%lld
", ans);
53     }
54     return 0;
55 }