poj 1769 Minimizing maximizer DP+线段树

缘起

日常浪费生命~ poj 1769 Minimizing maximizer

分析

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
Maximizer是一个接受n个数作为输入, 并输出他们的最大值的装置. 这个装置由m个叫做sorter的装置依次连接
而成. 第k个sorter把第k-1个sorter的输出作为输入. 然后将第sk到第tk个值进行排序之后，保持其余部分不变
输出. Maximizer的输入就是第一个sorter的输入. 最后一个sorter输出的第n个值就是Maximizer的输出.
从组成Maximizer的sorter中去掉几个之后, Maximizer有可能还可以正常工作. 现在给定sorter的序列. 求
其中的最短的一个子序列（可以不连续）使得Maximizer仍然可以正常工作。

【输入】
第一行包含n和m（2 <= n <= 50000, 1 <= m <= 500000）， 然后m行就是刻画这些个sorter的.
每行两个数, 分别就是sk和tk. 1 <= sk < tk <= n

【输出】
最短的长度.

【样例输入】
40 6
20 30
1 10
10 20
20 30
15 25
30 40

【样例输出】
4

【限制】
5s

显然，样例的答案是保留 [1,10]、[10,20]、[20, 30]、[30,40] 这四个sorter就够了. 因为不论你最大值在哪里, 总能将最大的冒泡到最后那个位置. 注意, 这些sorter的顺序必须是按照输入数据的顺序. 不能随意排的.

本题首先注意到, 我们完全可以假设最大值放在首位. 因为如果最大值在首位都可以被移动到末尾进行输出的话, 则不论它在哪个位置都是可以最后变动到末位的.

令

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
dp[i][j] 是经过i个sorter, 最大值从第1位出发移动到了第j位需要的最少的sorter数量.则dp[m][n]就是答
案, 并且我们有如下初始化
dp[0][1] = 0; // 因为一开始我们就假设最大值放在首位
dp[0][j] = INF; j>1 //不经过任何sorter, 最大值是不能跑到任何大于1的位置的.
下面考虑dp[i][j]
如果j!=ti的话, 则考虑第i个sorter, 这个sorter一定是无足轻重的.因为你最终的目标是位置j, 但是j!=ti
所以 dp[i][j]=dp[i-1][j]
如果j==ti的话, 则分2种情况
第一种情况, 没用第i个sorter. 则dp[i][j]=dp[i-1][j]
第二种情况, 用了第i个sorter. 则最大值在使用第i个sorter之前到达的位置就可以<j=ti,但是要>=si
不然的话, 就没办法借助[si,ti]将最大值推送到j=ti去. 所以
dp[i][j]=min{dp[i-1][j], min{dp[i-1][j'] | si<=j'<=ti}+1}
也就是

dp[0][1]=0, dp[0][j]=inf, j>1
dp[i][j]=dp[i-1][j], 当j!=ti的情况下
dp[i][j]=min{dp[i-1][j], min{dp[i-1][j'] | si<=j'<=ti}+1}, 当j==ti的情况下

ps: 《挑战程序设计》 P207 写错了，害得我看了半天~ 当时我就怎么看怎么别扭~

鉴于空间复杂度过高——O(n*m), 所以我们使用滚动数组进行优化:

1
2
dp[1]=0, dp[j]=inf, j>1
dp[ti]=min{dp[ti], 区间[si,ti]上的dp最小值+1}

但是观照上述dp方程发现——虽然空间复杂度降下来了，但是时间复杂度依旧为O(n*m), 即我们依旧是会被T掉的.

怎么办呢? 再次观察上述DP 方程. 诶~ 区间最小~ RMQ? 而且是区间更新的RMQ问题. 做RMQ一般是ST或者线段树. 因为带更新. 所以ST是不合适的. 所以本题应该使用线段树优化.

ps: 一般使用线段树、堆或者其他什么数据结构进行优化，例如对DP进行优化（例如dijkstra、prim的堆优化），指的是其中一个运算（例如这里的求区间最小）进行优化. 而不是说这些数据结构作为算法的主体思想. 算法的主体思想不是这些数据结构，而是DP之类的

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
//#include "stdafx.h"

#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
//#define LOCAL

const int maxm = 500005, maxn = 50005;
int n,m, dp[maxn], s[maxm], t[maxm];

struct SegTreeNode
{
	int begin, end, val; // val 是 dp[begin, end]上的最小值
}segTree[maxn<<2];

void build(int begin, int end, int cur)
{
	segTree[cur].begin = begin, segTree[cur].end = end;
	if (begin==end) // 点线段树
	{
		segTree[cur].val = dp[begin];
		return;
	}
	int mid = (begin+end)>>1;
	build(begin, mid, cur<<1);
	build(mid+1, end, cur<<1|1);
	segTree[cur].val = min(segTree[cur<<1].val, segTree[cur<<1|1].val);
}

int rmq(int begin, int end, int cur) // rmq询问
{
	if (begin==segTree[cur].begin && end==segTree[cur].end)
	{
		return segTree[cur].val;
	}
	int mid = (segTree[cur].begin+segTree[cur].end)>>1;
	if (end<=mid)
	{
		return rmq(begin, end, cur<<1);
	}
	else if (begin>mid)
	{
		return rmq(begin, end, cur<<1|1);
	}
	else
	{
		return min(rmq(begin, mid, cur<<1), rmq(mid+1, end, cur<<1|1));
	}
}

void updata(int i,int cur) // 维护线段树
{
	segTree[cur].val = min(segTree[cur].val, dp[i]);
	if (segTree[cur].begin==i && segTree[cur].end==i)
	{
		return;
	}
	int mid = (segTree[cur].begin+segTree[cur].end)>>1;
	if (i<=mid)
	{
		updata(i, cur<<1);
	}
	else
	{
		updata(i, cur<<1|1);
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	while(~scanf("%d%d", &n,&m))
	{
		for (int i = 1; i<=m; i++)
		{
			scanf("%d%d", s+i, t+i);
		}
		memset(dp, 0x3f, sizeof(dp));
		dp[1] = 0; // 初始化
		build(1,n,1); // 建树
		for (int i = 1,kk; i<=m; i++)
		{
			kk = min(dp[t[i]], rmq(s[i], t[i], 1)+1);
			if (kk<dp[t[i]]) // 如果真的变了, 才去维护线段树
			{
				dp[t[i]] = kk;
				updata(t[i],1); // logn时间维护线段树
			}
		}
		printf("%d\n", dp[n]);
	}
	return 0;
}

ac情况（水过水过~ 跑了1s~ 真慢!）

Status Accepted
Time 1000ms
Memory 5776kB
Length 1761
Lang C++
Submitted 2019-09-20 06:47:02
Shared
RemoteRunId 20877415

后继

唉~ DP还是没感觉~ 老是想不出来~