51Nod 1022 石子归并 V2 环形区间DP

缘起

【1】中我们研究了直线上的石子合并问题, 现在来研究环形上的石子合并问题. 并且研究一下区间DP的四边形优化. 51Nod 1022 石子归并 V2 至于为什么要使用四边形优化, 是因为【1】中的算法是O(n^3)的，而这里n=1000. 会T掉的. 而区间DP的四边形优化可以将时间复杂度优化到O(n^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
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 <= 1000)
第2 - N + 1：N堆石子的数量（1 <= A[i] <= 10000)
输出
输出最小合并代价

输入样例
4
1
2
3
4

输出样例
19

首先不是所有的区间DP都可以使用四边形优化的. 关于区间DP的四边形优化可以参见赵爽菊苣的论文. 只需要看懂第一章就行了（本蒟蒻表示并不难懂）.

关于本题, 和【1】的区别是【1】是直线石子合并, 而本题是环形石子合并， 所以需要倍增，即将区间变为 [1,…,2n], 其中 a[n+1,…,2n]=a[1,…,n]

则转换为[1,…,2n]这条直线上的石子合并问题. 最后的答案是min{dp[1][n],….,dp[n][2n-1]}

dp意义和【1】是一样的.

显然，本题的w[i,j] 函数是部分和, 所以满足四边形不等式的两个要求, 所以本题可以使用四边形优化到O(n^2)

即dp公式变成论文的(1.6), 其中论文中的m(i,j)就是本题的dp[i][j]

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

const int maxn = 2005; // 数组扩倍
int n, dp[maxn][maxn], a[maxn], w[maxn],s[maxn][maxn], inf = ~0u>>1;

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);
		a[i+n] = a[i]; // 数组扩倍
	}
	for (int i = 1; i<=n*2; i++)
	{
		w[i] = w[i-1]+a[i];
	}
	for (int i = 1; i<n*2; i++)
	{
		s[i][i+1] = i+1;
		dp[i][i+1] = w[i+1]-w[i-1];
	}
	for (int i = n*2-1; i; i--) // 和【1】一样, i是逆向的
	{
		for (int j = i+2; j<=n*2; j++)
		{
			dp[i][j] = inf, s[i][j] = 0;
			for (int k = s[i][j-1],t; k<=s[i+1][j]; k++) // 四边形优化区间DP
			{
				if (dp[i][j]>=(t=dp[i][k-1]+dp[k][j]+w[j]-w[i-1]))
				{
					dp[i][j] = t;
					s[i][j] = k; // 维护s[i][j]
				}
			}
		}
	}
	int ans = inf;
	for (int i = 1;i<=n; i++)
	{
		ans = min(ans, dp[i][i+n-1]);
	}
	printf("%d", ans);
	return 0;
}

ac情况

1
2
3
yfs
2019/10/3 21:08:01 C++ 78ms
29,300KB Accepted

参考

【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/