51Nod 1023 石子归并 V3 GarsiaWachs算法

缘起

【1】中我们学习了经典的区间DP问题——石子合并问题, 现在来研究其进阶版. 1023 石子归并 V3

分析

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
N堆石子摆成一条线。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一
堆石子数记为该次合并的代价。计算将N堆石子合并成一堆的最小代价。

例如： 1 2 3 4，有不少合并方法
1 2 3 4 => 3 3 4(3) => 6 4(9) => 10(19)
1 2 3 4 => 1 5 4(5) => 1 9(14) => 10(24)
1 2 3 4 => 1 2 7(7) => 3 7(10) => 10(20)

括号里面为总代价可以看出，第一种方法的代价最低，现在给出n堆石子的数量，计算最小合并代价。


输入
第1行：N（2 <= N <= 50000)
第2 - N + 1：N堆石子的数量（1 <= A[i] <= 10000）

输出
输出最小合并代价

输入样例
4
1
2
3
4

输出样例
19

限制
2s

和【1】相比，唯一的区别在于这里n的范围由100变成了50000. 这将导致【1】中的算法根本性的改变. 因为【1】中的算法如果照搬到这里的话, 不论是时间复杂度还是空间复杂度都是不能承受的. 而且也不能使用【2】中的四边形优化, 因为即便是四边形优化之后, 时空复杂度依旧是不能承受的.

所以来学习 GarsiaWachs算法. 貌似这种算法是专门为石子合并准备的. 复杂度是O(n^2). 其步骤如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
设序列是stone[1,...,n]（其中stone[0]和stone[n+1]是正无穷），从左往右，
找第一个k使stone[k-1]<=stone[k+1]
然后合并stone[k]和stone[k-1]，记下这个和sum，从当前位置开始向左找第一个满足stone[j]>sum的j，
把sum插到j后面

重复上述步骤，直到只剩下一堆石子.

举个例子：
186 64 35 32 103
因为35<103，所以最小的k是3，我们先把35和32删除，得到他们的和67，并向前寻找一个第一个超过67的数，把67插入到他后面
186 64（k=3,A[3]与A[2]都被删除了） 103
186 67（遇到了从右向左第一个比67大的数，我们把67插入到他后面） 64 103
186 67 64 103 （有定理保证这个序列的答案加上67就等于原序列的答案）
现在由5个数变为4个数了，继续！
186 （k=2,67和64被删除了）103
186 131（就插入在这里） 103
186 131 103
现在k=2（别忘了，设a[0]和a[n+1]等于正无穷大）
234 186
420
最后的答案呢？就是各次合并的重量之和呗。420+234+131+67=852，哈哈，算对了。

证明略，我这个辣鸡咱也不会证, 咱也不敢证. 瞬间此题变成模拟题——考验代码实现能力

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
//#include "stdafx.h"
#include <stdio.h>
//#define LOCAL

typedef long long LL;

const LL maxn = 50005, inf = ~0ull>>1;
LL n;

struct Node
{
	LL x;
	Node *prev, *nxt;
	Node(LL x):x(x), prev(0), nxt(0){}
}*head, *tail; // 双向链表

bool ok(Node *p)
{
	return p->nxt->x>=p->prev->x;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//	freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%lld", &n);
	head = new Node(inf);
	tail = head;
	for (LL i = 1,x; i<=n; i++)
	{
		scanf("%lld", &x);
		Node* p = new Node(x);
		tail->nxt = p;
		p->prev = tail;
		tail = p; // 尾插法
	}
	Node *p = new Node(inf);
	tail->nxt = p;
	p->prev = tail;
	tail = p; // 保证头尾都是inf节点
	LL ans = 0;
	while(n>1) // 只要剩下的石子堆数>1
	{
		Node *p = head->nxt;
		while(p!=tail)
		{
			if (ok(p))
			{
				break;
			}
			p = p->nxt;
		} // p就是满足条件的第一个k使stone[k-1]<=stone[k+1]
		Node *q = p;
		LL sum = p->x+p->prev->x; // 合并stone[k]和stone[k-1]，记下这个和sum
		n--; // 因为合并, 所以石子堆数-1
		ans+=sum;
		while(p!=head)
		{
			if (p->x>sum)
			{
				break;
			}
			p = p->prev;
		} // 找到第一个>sum的节点p
		Node *t = new Node(sum);
		p->nxt->prev = t;
		t->nxt = p->nxt;
		p->nxt = t;
		t->prev = p; // 将sum插入到p的后面
		q->nxt->prev = q->prev->prev;
		q->prev->prev->nxt = q->nxt; // 移除q和q前面这2个节点.
	}
	printf("%lld", ans);
	return 0;
}

用链表模拟上述过程, 但是被T掉了, 但是估计算法输出的答案都是正确的. 仔细想想上述算法到底哪里慢了? 至少有以下2个优化点

  1. 用数组而不是链表, 因为链表总是要new Node, 而这个过程是比较耗时的
  2. 每次真的要从头开始遍历吗? 即代码47行. 其实不需要啊, 因为GarsiaWachs算法循环的每次不就是删掉2个顶点, 插入一个顶点吗? 其实只需要从插入处开始往后考察即可.

基于上述2点优化, 我们可以再写一版

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
//#include "stdafx.h"
#include <stdio.h>
//#define LOCAL

typedef long long LL;
const int maxn = 50005;
LL n, tot, inf= ~0ull>>1, ans,tail, head;
struct Node
{
	LL x, prev, nxt;
}ns[maxn<<2]; // 因为合并石子过程中也可能产生新的石子, 所以数组不能仅仅是5w

bool ok(LL i) // 检测ns[i]是否可以?
{
	return ns[ns[i].prev].x<=ns[ns[i].nxt].x;
}

LL process(LL &i) // 删除2个点, 更新答案, 更新i为它前面2个节点
{
	LL sum = ns[i].x+ns[ns[i].prev].x;
	ans+=sum, n--;
	LL j = ns[i].nxt; //i的后一个节点
	i = ns[ns[i].prev].prev; // 找到ns[i]这个节点的前前节点
	ns[i].nxt =j;
	ns[j].prev= i; // 删除两个节点
	return sum;
}

void build() // 构建链表
{
	head = 1, tail = 1; // 先检查head处, 如果head处不行,再跳到tail处,从tail处开始往后检查
	ns[1].x = inf;
	tot = 1;ans =0;
	for (LL i = 1,x;i<=n; i++)
	{
		scanf("%lld", &x);
		++tot;
		ns[tot].x = x;
		ns[tot].prev = tail; // 尾插法
		ns[tail].nxt = tot;
		tail = tot;
	}
	++tot;
	ns[tot].x = inf;
	ns[tot].prev = tail;
	ns[tail].nxt = tot;
	tail = tot; // 构建初始链表结束
}

void processhead(LL sum)
{
	while(ns[head].x<=sum)
	{
		head = ns[head].prev;
	} // 找到了>sum的节点ns[head]
	tot++;
	ns[tot].x = sum;
	ns[tot].nxt = ns[head].nxt;
	ns[ns[head].nxt].prev = tot;
	ns[head].nxt = tot;
	ns[tot].prev = head; // 插入合并后的石子堆
	if (head==1)
	{
		head = ns[1].nxt;
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	while(~scanf("%lld", &n))
	{
		build(); // 构建链表
		LL t;
		head = 2; // 从第一个节点开始考察
		while(n>1)
		{
			t = head;
			while(!ok(t))
			{
				t = ns[t].nxt;
			}
			LL sum = process(t);
			head = t;
			processhead(sum);
		}
		printf("%lld\n", ans);
	}
	return 0;
}

但是遗憾的是——还是被T掉了. 但是比较好的事情是, 上一版被T掉的时间长达6s才出答案, 但是这一版提高到了3s. 说明上述2点优化是有效的.

那么该怎么办呢? 我甚至有点绝望了. 因为能想到的优化都想到了, 别跟我说网上很多递归代码，哪些代码写的比较玄学，我又看不懂. 直至我看到了【3】， 我特么给跪了——纯暴力模拟. 而且大量的移动复制数组. 而且比我在本机上慢~ 但是那又怎么样? 人家依旧风骚的过了!!! 我特么真的不懂51nod的判题程序了.

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
//#include "stdafx.h"
#include <stdio.h>
#include <algorithm>
using namespace std;
//#define LOCAL
typedef  long long LL;
LL n, a[50005], inf = ~0ull>>1,k,ans;

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d", &n);
	for (LL i = 1;i<=n; i++)
	{
		scanf("%lld", a+i);
	}
	a[0] = a[n+1]=inf; // 头尾都是inf
	while(n>1)
	{
		for (LL i = 1; i<=n; i++)
		{
			if (a[i-1]<=a[i+1])
			{
				k = i;
				break;
			}
		} // 找到第一个a[k-1]<=a[k+1]
		a[k-1]+=a[k];
		ans+=a[k-1];
		for (LL i = k; i<n; i++)
		{
			a[i] = a[i+1];
		} // 对,你没看错, 就是这么暴力的删除a[k].
		k--; // 来到了a[k-1], 我们下一步是将a[k-1]通过不断的交换移动到前面去, 类似于冒泡
		while(a[k-1]<=a[k])
		{
			swap(a[k-1], a[k]);
			k--;
		} // 对, 你也没看, 就是这么暴力的将2数之和移动到了该移动的位置处.
		a[n] =inf; // 新的尾部
		n--; // 石子堆数-1
	}
	printf("%lld\n", ans);
	return 0;
}

ac情况（真的是日了狗了~ 上面的代码绝壁比我写的慢~ 偏偏能过~ 可能是上面的代码及时的减少了n, 使得数组能跑的更快吧! 但是我的代码根本不涉及数组的大量移动啊~）

1
2
3
yfs
2019/10/4 16:35:51 C++ 1281ms
2,100KB Accepted

如果用到我上面提到的第二点优化的话, 代码能稍微快一点

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
//#include "stdafx.h"
#include <stdio.h>
#include <algorithm>
using namespace std;
//#define LOCAL
typedef  long long LL;
LL n, a[50005], inf = ~0ull>>1,k=1,ans;

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d", &n);
	for (LL i = 1;i<=n; i++)
	{
		scanf("%lld", a+i);
	}
	a[0] = a[n+1]=inf;
	while(n>1)
	{
		while(k<=n)
		{
			if (a[k-1]<=a[k+1])
			{
				break;
			}
			k++;
		} 
		a[k-1]+=a[k];
		ans+=a[k-1];
		for (LL i = k; i<n; i++)
		{
			a[i] = a[i+1];
		}
		k--;
		while(a[k-1]<=a[k])
		{
			swap(a[k-1], a[k]);
			k--;
		}
		k--; // 来到下一次考察的点
		if (!k)
		{
			k =1;
		} // k不能变到0去
		a[n] =inf;
		n--;
	}
	printf("%lld\n", ans);
	return 0;
}

ac情况

1
2
3
yfs
2019/10/4 16:44:17 C++ 1125ms
2,100KB Accepted

基本上稳定的比优化前快100+ms左右. 我就是死也想不通为什么我用数组模拟链表的写法会T? 明明在我本机环境跑的时候吊打纯数组暴力啊~

参考

【1】https://yfsyfs.github.io/2019/10/03/51Nod-1021-%E7%9F%B3%E5%AD%90%E5%BD%92%E5%B9%B6-%E7%BB%8F%E5%85%B8%E5%8C%BA%E9%97%B4DP/

【2】https://yfsyfs.github.io/2019/10/03/51Nod-1022-%E7%9F%B3%E5%AD%90%E5%BD%92%E5%B9%B6-V2-%E7%8E%AF%E5%BD%A2%E5%8C%BA%E9%97%B4DP/

【3】https://www.cnblogs.com/lwq12138/p/5425465.html