放牧代码和思想
专注自然语言处理、机器学习算法
    愛しさ 優しさ すべて投げ出してもいい

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和值

最优解

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

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #2

    博主好, 5 4 3 2 1 2按照题意答案应该是1, 但是我运行了你的程序后答案是7,说明你的程序求的是非严格递增所需要花费的最小价值。 ==

    happyboy9年前 (2015-08-20)回复
  2. #1

    Hello,好久没来,小站改名为:静水流深,网址不变,还望改一下友链名称,3Q

    Defel11年前 (2014-02-13)回复
    • 改好了,不用客气

      hankcs11年前 (2014-02-13)回复

我的作品

HanLP自然语言处理包《自然语言处理入门》