POJ 3666 Making the Grade dp

缘起

哎，dp啊，做的还是不够! 能力还是太差!!! POJ 3666 Making the Grade

分析

题意还是比较好懂的.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
给你一个[0,1e9]范围内的整数序列{a1,...,an}. 将该序列修改成{b1,...,bn}.  修改的代价是
cost=|a1-b1|+...+|an-bn|
求将给定的序列{a1,...,an}改成一个单调递增的序列的最小代价.

【输入】
第一行是序列的元素个数n(<2000), 第二行是n个[0,1e9]范围内的整数.

【输出】
改造的最小代价

【样例输入】
7
1
3
2
4
5
3
9

【样例输出】
3

【限制】
1s

【hint】
将 a3改造成3, a6改造成5, 则代价为 |3-2|+|3-5|=3

dp

1
2
3
4
5
6
7
令dp[i][j]为a[1,...,i]修改为单增序列并且最大值（即末尾元素）为j的最小代价（妈的,还是没想到!）
则不难给出（要取min的，不然你晓得a[1,...,i-1]的末尾元素变成什么是最小的?）
dp[i][j]=|a[i]-j|+min_{k<=j}dp[i-1][k], 2<=i<=n
ps: 这里多说一句，一开始我令dp[i][j]为a[1,...,i]修改为以a[j](1<=j<=i)为末尾元素的最小代价. 
则dp方程变成
dp[i][j]=|a[i]-a[j]|+min_{k<=i-1,a[k]<=a[j]}dp[i-1][k], 2<=i<=n
这个dp方程就比上面的难求多了! 所以有的时候, 对什么进行dp很重要!

而且不难注意到，其实 min_{k<=j}dp[i-1][k] 是可以同步更新的——不需要O(n)时间维护，只需要O(1)时间维护, 所以总体复杂度是O(NM), 其中M是a数列的值的范围——但是多大10亿. 这就是题目的目的——让你即便想出了dp的方程也不能直接使用，必须要做空间优化. 而空间优化的方法也是极为明显的——2000比10亿小多了!

所以要改变dp的对象

1
2
3
4
5
6
7
令b为a的升序排序
令dp[i][j]为a[1,..,i]修改为以b[j]为末尾元素的最小代价（注意,不难直觉意识到, 末尾元素一定是原序列中
既有的元素）. 
则dp方程
dp[i][j]=|a[i]-b[j]|+min_{k<=j}dp[i-1][k], 2<=i<=n,1<=j<=n
而初始值
dp[1][j] = |b[j]-a[1]|, 1<=j<=n

最后，答案就是 dp[n][1],…,dp[n][n] 中最小的. 然后用滚动数组将j滚动掉进行空间复杂度的优化，得到下面的ac代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
//#include "stdafx.h"

#include <stdio.h>
#include <algorithm>
using namespace std;
#define ABS(a,b) ((a)>(b)?((a)-(b)):((b)-(a)))
//#define LOCAL

int n, a[2005], b[2005], dp[2005][2005];

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d", &n);
	for (int i = 1; i<=n;i++)
	{
		scanf("%d", a+i);
		b[i] = a[i];
	}
	sort(b+1,b+n+1);
	for (int j = 1; j<=n;j++)
	{
		dp[1][j] = ABS(b[j], a[1]);
	} // 初始化
	for (int i = 2,t; i<=n; i++)
	{
		t = ~0u>>1;
		for (int j = 1; j<=n;j++)
		{
			t = min(t, dp[i-1][j]);
			dp[i][j] = ABS(a[i], b[j])+t;
		}
	}
	int ans = ~0u>>1;
	for (int i = 1; i<=n;i++)
	{
		ans = min(ans, dp[n][i]);
	}
	printf("%d\n", ans);
	return 0;
}

ac情况

Status Accepted
Time 47ms
Memory 15816kB
Length 734
Lang C++
Submitted 2019-08-28 16:12:32
Shared
RemoteRunId 20812096

显然，我们还可以使用滚动数组优化掉i 来节约空间复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
//#include "stdafx.h"

#include <stdio.h>
#include <algorithm>
using namespace std;
#define ABS(a,b) ((a)>(b)?((a)-(b)):((b)-(a)))
//#define LOCAL

int n, a[2005], b[2005], dp[2005];

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d", &n);
	for (int i = 1; i<=n;i++)
	{
		scanf("%d", a+i);
		b[i] = a[i];
	}
	sort(b+1,b+n+1);
	for (int j = 1; j<=n;j++)
	{
		dp[j] = ABS(b[j], a[1]);
	} // 初始化
	for (int i = 2,t; i<=n; i++)
	{
		t = ~0u>>1;
		for (int j = 1; j<=n;j++)
		{
			t = min(t, dp[j]);
			dp[j] = ABS(a[i], b[j])+t;
		}
	}
	int ans = ~0u>>1;
	for (int i = 1; i<=n;i++)
	{
		ans = min(ans, dp[i]);
	}
	printf("%d\n", ans);
	return 0;
}

ac情况

Status Accepted
Time 32ms
Memory 112kB
Length 714
Lang C++
Submitted 2019-08-28 16:14:52
Shared
RemoteRunId 20812104

显然——空间复杂度由15MB优化到了 112KB