SGi's Blog

链型石子合并

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']
故石子合并可利用四边形不等式进行优化。