学步园

石子合并问题分析(转)

链型石子合并

n(n<=3000)
堆石子排成一条直线，每堆石子有一定的重量。现在要合并这些石子成为一堆石子，但是每次只能合并相邻的两堆。每次合并需要消耗一定的体力，该体力为所合并的两堆石子的重量之和
。问最少需要多少体力才能将n
堆石子合并成一堆石子？

样例输入:
8
5 2 4 7 6 1 3 9

样例输出
105

来源：经典问题

分析：

令f[i,j
]
表示归并第i

个数到第j
数的最小代价,sum[i,j
]
表示第i

个数到第j
个数的和，这个可以事先计算出来。sum[i,j
]
可以在O(1)
的时间内算出.

容易的到以下的动态转移方程：

阶段：以归并石子的长度为阶段，一共有n-1
个阶段。

状态：每个阶段有多少堆石子要归并，当归并长度为2
时，有n-1
个状态；

当归并长度为3
时，有n-2
个状态；

当归并长度为n
时，有1
个状态。

决策：当归并长度为2
时，有1
个决策；当归并长度为3
时，有2
个决策；

当归并长度为n
时，有n-1
个决策。

环型石子合并

问题描述

在一个圆形操场的四周摆放着n
堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2
堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。

试设计一个算法，计算出将n
堆石子合并成一堆的最小得分和最大得分。

输入文件

输入文件stone.in

包含两行，第1
行是正整数n(1
≤n
≤100)
，表示有n
堆石子。第2
行有n
个
整数，分别表示每堆石子的个数。

输出文件

输出文件stone.out


包含两行，第1
行中的数是最小得分；第2
行中的数是最大得分。

输入样例
4
4 4
5 9

输出样例
43
54

分析：

用sum[i,j
]
表示将从第i

颗石子开始的接下来j
颗石子合并所得的分值，
fmax
[i,j
]
表示将从第i

颗石子开始的接下来j
颗石子合并可能的最大值，那么：
fmax
[i,j
] = max(fmax[i, k]
+ fmax
[i
+ k, j ? k] + sum[i,k
] + sum[i+k, j?k]) (2<=k<=j)
fmax
[i,1] = 0

同样的，我们用fmin

[i,j
]
表示将第从第i

颗石子开始的接下来j
颗石子合并所得的最小值，可以得到类似的方程：
fmin
[i,j
] = min(fmin[i, k]
+ fmin
[i
+ k, j ? k] + sum[i,k
] + sum[i+k, j? k]) (0<=k<=j)
fmin
[i,0] = 0

这样，我们完美地解决了这道题。时间复杂度也是O(n^2)
。

O(n^3)
的Pascal
代码

拓展：四边形不等式优化

首先先说一下四边形不等式与决策单调性的结论：

凸性

当函数w[i,j
]
满足：w[i,j] + w[i',j
'] <= w[i;,j
] + w[i,j
'] (i
<=i

’
<j<=j
’
)
时，称w
满足四边形不等式。

单调性

当函数w[i,j
]
满足：w[i',j] <= w[i,j
'] (i
<=i

’
<j<=j
’
)
时，称w
满足关于区间包含的单调性。

这样，对于状态转移方程式
m[i,j
]=min{m[i,k-1]+m[k,j
]+w[i,j
]} (i
<k<=j)
如果w[i,j
]
满足四边形不等式和区间包含单调性，那么m[i,j
]
也满足四边形不等式。

用s[i,j
]
表示m[i,j
]
的决策，如果函数m[i,j
]
满足四边形不等式，则函数s[i,j
]
满足单调性，即决策单调性：

s[i,j]<=s[i,j+1]<=s[i+1,j+1]
。

则函数s[i,j
]
的值应该在一个区间内，即：

s[

i,j-1] <= s[i,j
] <=
s[i+1,j]

由于s[i,j-1]
和s[i+1,j]
已经在阶段
j-i

求出，所以在枚举决策变量k
时，就可以从s[i,j-1]
到s[i+1,j]
。

于是，我们利用s[i,j
]
的单调性，得到经过优化的状态转移方程为：

利用这样的决策单调性，就可以把时间复杂性优化到O(n^2)
。

边界：s[i,i
] = i

s[i,j
]
的值在m[i,j
]
取得最优值时，保存、更新

例如，对石子归并这道题，先验证w[i,j
]
满足区间单调性和四边形不等式。对数据
i
i

’
j j
’

2 3 7 4 6 5

单调性：
w[i',j
] = 3+7+4=14
w[i,j
'] =2+3+7+4+6+5=27

故w[i',j
] <= w[i,j
']
满足单调性

四边形不等式：
w[i,j
] + w[i',j
'] =
(2+3+7+4) + (3+7+6+5) = 16+21 = 37
w[i',j
] + w[i,j
'] = (3+7+4)
+ (2+3+7+4+6+5) = 14 + 27 = 41

故 w[i,j
] + w[i',j
'] <= w[i',j
] + w[i,j
']

故石子合并可利用四边形不等式进行优化。

转自:http://www.gzlfdn.cn/article.php?id=218