石子合并问题分析(转)
链型石子合并
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 个决策。
1
2
3
4
5
6
for len := 2 to n do
for i := 1 to n - len + 1 do begin
j := i + len - 1 ;
f[ i, j ] := MAXLONGINT;
for k := i+ 1 to j do begin
参考上面状态转移方程求解
环型石子合并
问题描述 在一个圆形操场的四周摆放着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 代码
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
var
fmin, fmax, sum : array [ 1..100, 1..100] of longint ;
num : array [ 1..100] of longint ;
i, j, k, x, t, n, max, min : longint ;
begin
readln ( n) ;
for i := 1 to n do begin
read ( num[ i ]) ;
sum[ i, 1 ] := num[ i ] ;
fmin [ i, 1 ] := 0;
fmax [ i, 1 ] := 0;
end ;
for j := 2 to n do
for i := 1 to n do
sum[ i, j ] := num[ i ] + sum[ i mod n + 1 , j- 1 ] ;
for j := 2 to n do
for i := 1 to n do begin
fmin [ i, j ] := maxlongint ;
fmax [ i, j ] := - maxlongint;
t := sum[ i, j ] ;
for k := 1 to j- 1 do begin
x := ( i+ k- 1 ) mod n + 1 ;
if ( fmin [ i, k ] + fmin [ x, j - k] + t < ; fmin [ i, j ]) then
fmin [ i, j ] := fmin [ i, k ] + fmin [ x, j - k] + t;
if ( fmax [ i, k ] + fmax [ x, j - k] + t > ; fmax [ i, j ]) then
fmax [ i, j ] := fmax [ i, k ] + fmax [ x, j - k] + t;
end ;
end ;
max := - maxlongint ;
min := maxlongint ;
for j := 1 to n do begin
if fmin [ j, n ] < min then
min := fmin [ j, n ] ;
if fmax [ j, n ] > ; max then
max := fmax [ j, n ] ;
end ;
writeln ( min) ;
writeln ( max) ;
end .
拓展：四边形不等式优化
首先先说一下四边形不等式与决策单调性的结论：
凸性 当函数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
