POJ 3666 Making the Grade 题解 《挑战程序设计竞赛(第2版)》

POJ 3666 Making the Grade

农夫约翰想修一条尽量平缓的路，路的每一段海拔是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状态方程的转移：

记原数组为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//////////////////////////////////

不过我们可以做得更好，注意到每次都是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//////////////////////////////////

空间复杂度的降低立竿见影。

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 3666 Making the Grade 题解 《挑战程序设计竞赛(第2版)》