农夫约翰想修一条尽量平缓的路,路的每一段海拔是A_i,修理后是B_i,花费|A_i – B_i|,求最小花费。
平缓的意思是海拔单调增或单调减(非严格,下同),放在《2.3 记录结果再利用的“动态规划” 需稍加思考的题目》的主要目的大概是让我们破解这个“到底是增好还是减好”的局。
这道题目用DP的话可以完全忽略这个局,达到破局的效果:
dp[i][j] := 前i + 1个数变成单调且最后一个数是B[j],此时的最小成本
dp[i][j] = min(dp[i – 1][k]) + |A[i] – B[j]| (k = 0…j)
比如对于1 3 2这个序列,dp如下:
dp和值 |
最优解 |
dp[0][0] = 0 |
1 |
dp[0][1] = 1 |
2 |
dp[0][2] = 2 |
3 |
dp[1][0] = 2 |
3 1 |
dp[1][1] = 1 |
1 2 |
dp[1][2] = 0 |
1 3 |
dp[2][0] = 3 |
1 1 1 |
dp[2][1] = 1 |
1 2 2 |
dp[2][2] = 1 |
1 3 3 |
举个栗子说明dp状态方程的转移:
记原数组为A = 1 3 2,升序后的数组为B = 1 2 3,降序后的数组为C = 3 2 1
dp[2][1] = min{dp[1][0], dp[1][1]} + abs(2 – 2)
——在保留dp[1][1]对应的最优解1 2的情况下,将B[1]=2添加到尾部得到 1 2 2,单调增
dp[2][2] = min{dp[1][0], dp[1][1],dp[1][2]} + abs(2 – 3)
——在保留dp[1][2]对应的最优解1 3的情况下,将B[2]=3添加到尾部得到 1 3 3,单调增
有读者指出“程序求的是非严格递增所需要花费的最小价值”,是我没想全面,下面的代码是侥幸过关的,仅供参考。
#include <iostream> #include <algorithm> using namespace std; int A[2000 + 16]; int B[2000 + 16]; int dp[2000 + 16][2000 + 16]; // dp[i][j] := 前i + 1个数变成单调且最后一个数是B[j],此时的最小成本 ///////////////////////////SubMain////////////////////////////////// int main(int argc, char *argv[]) { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif int N; cin >> N; for (int i = 0; i < N; ++i) { cin >> A[i]; } memcpy(B, A, N * sizeof(int)); sort(B, B + N); for (int j = 0; j < N; ++j) { dp[0][j] = abs(A[0] - B[j]); } for (int i = 1; i < N; ++i) { int pre_min_cost = dp[i - 1][0]; // dp[i - 1][0...j]的最小值 for (int j = 0; j < N; ++j) { pre_min_cost = min(pre_min_cost, dp[i - 1][j]); dp[i][j] = pre_min_cost + abs(A[i] - B[j]); // 前一个最优解(长i-1 + 1)的基础上,加入B[j]凑成长i+1 } } cout << *min_element(dp[N - 1], dp[N - 1] + N) << endl; #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); system("out.txt"); #endif return 0; } ///////////////////////////End Sub//////////////////////////////////
12511022 | hankcs | 3666 | Accepted | 16028K | 47MS | C++ | 1112B | 2014-02-11 00:37:09 |
不过我们可以做得更好,注意到每次都是dp[i]和dp[i-1]被用到,可以滚动数组。
#include <iostream> #include <algorithm> using namespace std; int A[2000 + 16]; int B[2000 + 16]; int dp[2][2000 + 16]; // dp[i][j] := 前i + 1个数变成单调且最后一个数是B[j],此时的最小成本 ///////////////////////////SubMain////////////////////////////////// int main(int argc, char *argv[]) { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif int N; cin >> N; for (int i = 0; i < N; ++i) { cin >> A[i]; } memcpy(B, A, N * sizeof(int)); sort(B, B + N); for (int j = 0; j < N; ++j) { dp[0][j] = abs(A[0] - B[j]); } for (int i = 1; i < N; ++i) { int cur = i & 0x1; int pre = (i - 1) & 0x1; int pre_min_cost = dp[pre][0]; // dp[i - 1][0...j]的最小值 for (int j = 0; j < N; ++j) { pre_min_cost = min(pre_min_cost, dp[pre][j]); dp[cur][j] = pre_min_cost + abs(A[i] - B[j]); // 前一个最优解(长i-1 + 1)的基础上,加入B[j]凑成长i+1 } } int cur = (N - 1) & 0x1; cout << *min_element(dp[cur], dp[cur] + N) << endl; #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); system("out.txt"); #endif return 0; } ///////////////////////////End Sub//////////////////////////////////
12511026 | hankcs | 3666 | Accepted | 252K | 63MS | C++ | 1175B | 2014-02-11 00:41:28 |
空间复杂度的降低立竿见影。
知识共享署名-非商业性使用-相同方式共享:码农场 » POJ 3666 Making the Grade 题解 《挑战程序设计竞赛(第2版)》
博主好, 5 4 3 2 1 2按照题意答案应该是1, 但是我运行了你的程序后答案是7,说明你的程序求的是非严格递增所需要花费的最小价值。 ==
感谢指正
Hello,好久没来,小站改名为:静水流深,网址不变,还望改一下友链名称,3Q
改好了,不用客气