[BZOJ 1592] Making The Grade路面修整

本文主要是介绍[BZOJ 1592] Making The Grade路面修整，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1592: [Usaco2008 Feb]Making the Grade 路面修整
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 704 Solved: 483
[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

3

HINT

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

这题显然是个 $DP$ ...

首先我们可以设置记忆化数组 $f_{i,j}$ ,代表前 $i$ 步可以取得的最大高度为 $j$ .因为高度的范围比较大但是数据个数不多所以考虑离散化一发.

离散化之后 $DP$ 转移方程还算明确

\[ f_{i,j}=min( f_{i,j-1}, f_{i-1,j}+ \left | a_i - b_j \right | )\]

其中 $a_i$ 为第 $i$ 个路段的高度, $b_i$ 的意义是若某路段的高度在离散化后的结果为 $i$ ,则原数据为 $b_i$ .

然后由于题目要求可以单调不降或者单调不升, 所以应该扫描两遍然后取较小答案, 枚举 $j$ 时要一次正向一次反向.

然后参考代码如下:

GitHub

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <iostream>
 5 #include <algorithm>
 6 
 7 const int MAXN=2010;
 8 const int INF=0x3FFFFFFF;
 9 
10 int n;
11 int m;
12 int data[MAXN];
13 int hash[MAXN];
14 int dp[MAXN][MAXN];
15 
16 int Hash(int);
17 void Initialize();
18 int DynamicProgramming();
19 
20 int main(){
21     Initialize();
22     printf("%d\n",DynamicProgramming());
23     return 0;
24 }
25 
26 int DynamicProgramming(){
27     memset(dp,0x3F,sizeof(dp));
28     memset(dp[0],0,sizeof(dp[0]));
29     for(int i=1;i<=n;i++){
30         for(int j=1;j<=m;j++){
31             dp[i][j]=std::min(dp[i-1][j]+abs(hash[j]-data[i]),dp[i][j-1]);
32         }
33     }
34     int ans=dp[n][m];
35     memset(dp,0x3F,sizeof(dp));
36     memset(dp[0],0,sizeof(dp[0]));
37     for(int i=1;i<=n;i++){
38         for(int j=m;j>0;j--){
39             dp[i][j]=std::min(dp[i-1][j]+abs(hash[j]-data[i]),dp[i][j+1]);
40         }
41     }
42     ans=std::min(ans,dp[n][1]);
43     return ans;
44 }
45 
46 void Initialize(){
47     scanf("%d",&n);
48     for(int i=1;i<=n;i++){
49         scanf("%d",data+i);
50     }
51     memcpy(hash,data,sizeof(data));
52     std::sort(hash+1,hash+n+1);
53     m=std::unique(hash+1,hash+n+1)-(hash+1);
54 }
55 
56 inline int Hash(int x){
57     return std::lower_bound(hash+1,hash+m+1,x)-hash;
58 }