缘起
【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 <stdio.h>
#include <algorithm>
using namespace std;
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);
#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--)
{
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++)
{
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;
}
}
}
}
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/