A straight dirt road connects two fields on FJ's farm, but it changes elevation more than FJ would like. His cows do not mind climbing up or down a single slope, but they are not fond of an alternating succession of hills and valleys. FJ would like to add and remove dirt from the road so that it becomes one monotonic slope (either sloping up or down).
You are given N integers A1, ... , AN (1 ≤ N ≤ 2,000) describing the elevation (0 ≤ Ai ≤ 1,000,000,000) at each of N equally-spaced positions along the road, starting at the first field and ending at the other. FJ would like to adjust these elevations to a new sequence B1, . ... , BN that is either nonincreasing or nondecreasing. Since it costs the same amount of money to add or remove dirt at any position along the road, the total cost of modifying the road is
- | A 1 - B 1| + | A 2 - B 2| + ... + | AN - BN |
- Please compute the minimum cost of grading his road so it becomes a continuous slope. FJ happily informs you that signed 32-bit integers can certainly be used to compute the answer.
- Input
- * Line 1: A single integer: N
- * Lines 2..N+1: Line i+1 contains a single integer elevation: Ai
- Output
- * Line 1: A single integer that is the minimum cost for FJ to grade his dirt road so it becomes nonincreasing or nondecreasing in elevation.
- Sample Input
- 7 1 3 2 4 5 3 9
- Sample Output
- 3
这道题据说是有一点问题的, 因为它的测试数据就是求变成最小不上升的最小代价没有从大到小.
我们假设从第 1 个到最后一个的土地高度构成一个数组 A, 那么, 我们可以知道, 在修改后的数组 B 中, 所有的数都属于 A, 因为如果过高要挖低最少须和前面一样, 如果过低要拔高则最少须和前面一样, 由于前面的值为 A 中的值, 且其他情况不需要更改土地的高度, 所以 B 中所有的值均在 A 中出现过.
然后我们假设 dp[i][j]表示前 i 个土地中最大 (其实也就是第 i 块土地的高度) 是 A 数组从小到大排好序后第 j 大的数. 为什么要这样假设? 本题易得 (0 ≤ Ai≤ 1,000,000,000), 如果采用传统的方法 dp[i][j],i 表示前 i 种, j 表示最大的高度是 j, 那么算法复杂度就是 O(AN)由于 A 最大 1e9, 定会超时, 所以这道题解题的关键就是离散化解本题, 所谓的离散化(百度百科):
离散化, 把无限空间中有限的个体映射到有限的空间中去, 以此提高算法的时空效率.
通俗的说, 离散化是在不改变数据相对大小的条件下, 对数据进行相应的缩小. 例如:
原数据: 1,999,100000,15; 处理后: 1,3,4,2;
原数据:{100,200},{20,50000},{1,400};
处理后:{3,4},{2,6},{1,5};
我们把原来容易想到的 j 变成 A 数组从小到大排好序后第 j 大的数, 因为实际上最后的所有可能都是来自于 A 数组中的数, 这样我们就能不白白计算用不到的地方, 能在规定时间完成计算.
易得递推方程 dp[i][j] = min(dp[i - 1][k] + abs(a[i] - a[j])), 其中 (1 <= k <= j), 意思就是前 i 个土地使得最后一个土地的值为 j 时, 可以由前 i-1 块土地中最后一块土地(也就是第 i-1 块土地) 的高度小于等于 j 作为跳板, 把第 i 块土地高度变为 j 从而得到 dp[i][j]. 为了减少时间 (因为每次计算 min(dp[i - 1][k]) 也会花费 O(n)复杂度, 一起就是 O(n3)也是就 8e9 也会超时, 所以我们可以用一个变量去记载前 j-1 个的最小, 然后再和第 j 个比较, 这样就 O(1)就能得到前 j 个最小的.
AC 代码(参考思路:):
- #include <stdio.h>
- #include <algorithm>
- using namespace std;
- const int INF = 0x3fffffff;
- int a[2005];// 原数组
- int b[2005];// 原数组排完序的数组
- long long dp[2005][2005];//dp[i][j]前 i 个中第 i 块土地为 j 高度的最小花费
- long long min_old = INF;// 前 j - 1 项的最小值
- long long ans = INF;// 答案
- int main(void)
- {
- int n;
- scanf("%d", &n);
- for(int i = 0; i < n; i++)
- {
- scanf("%d", &a[i]);
- b[i] = a[i];
- }
- sort(b, b + n);
- for(int i = 0; i < n; i++)
- dp[0][i] = abs(b[i] - a[0]);// 一开始让第一块地值为 i, 所以 dp[0][i]均为 abs(b[i] - a[0]),b[i]: 排完序第 i 大高度, a[0]: 第一块地的初始高度
- for(int i = 1; i < n; i++)// 从 2 块地开始 (因为 i 从 0 开始) 到 n 块地
- {
- min_old = INF;// 初始化前 i - 1 块地的最大高度为 a[0]到 a[j - 1]时那一块最小
- for(int j = 0; j < n; j++)
- {
- min_old = min(min_old, dp[i - 1][j]);// 前 i - 1 块地的最大高度为 a[0]到 a[j - 1]时最小的花费与前 i - 1 块地最大高度为 a[j]时哪个花费小
- dp[i][j] = min_old + abs(b[j] - a[i]);
- }
- }
- for(int i = 0; i < n; i++)
- ans = min(ans, dp[n - 1][i]);// 答案就在前 n 块中第 n 块的高度为 a[i]时(因为最后一块什么高度都有可能, 都满足从小到大的条件, 答案只是取其中最小值)
- printf("%lld\n", ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3398293.html