定理

  • 定理一 当函数 $w(i,j)$ 满足 $w(i,j) + w(i’,j’) \leq w(i’,j) + w(i,j’) \; i \leq i’ \leq j \leq j’$时,则称函数w满足四边形不等式
  • 定理二 当函数 $w(i,j)$ 满足 $w(i’,j) \leq w(i,j’) \; i \leq i’ \leq j \leq j’$时,则称函数w关于区间包含关系单调
  • 定理三 若函数 $w(i,j)$ 满足上述两种关系,对于函数 $d(i,j) = min_{i \leq k < j }(d(i,k) + d(k+1,j)) + w(i,j)$,d也满足四边形不等式,d的决策 $s(i,j)$ 满足单调性,即 $s(i,j-1) \leq s(i,j) \leq s(i+1,j) \; i \leq j$

这样对于区间$(i,j)$,$k$的决策范围就被限定在$s(i,j-1)$ 与 $s(i+1,j)$之间
复杂度由 $O(n^3)$ 降为 $O(n^2)$

应用

一般可以应用与以下两种方程

  • $d_{i} = min_{j < i} d_{j} + w(i,j)$
  • $d(i,j) = min_{i \leq k < j }(d(i,k) + d(k+1,j)) + w(i,j)$

题目

uva10304

求最优二叉排序树

很显然 $w_{i,j} = \sum_{k=i}^j{e_k}$ 满足四边形不等式和区间包含关系单调

  • $d(i,j) = min_{s(i,j-1) \leq k \leq s(i+1,j) }(d(i,k-1) + d(k+1,j)) + w(i,j) - e(k)$

poj1160

多邮局选址问题

对于一个区间,邮局放在中点是最优的
设 $d(i,j)$ 表示前j个点有i个邮局最优值

$d(i,j) = min_{s(i-1,j) \leq k \leq s(i,j+1) }(d(i-1,k) + w(k+1,j)) \; s(1,j) = 0,s(1,n+1) = n$

$w(i,j)$ 可以用$O(n^2)$的递推预处理出来

1
2
F(i,1,n) F(j,i+1,n)
cost[i][j] = cost[i][j-1] + x[j] - x[(i+j)>>1];

注意循环时先i后j,j用逆序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
fll(d,INF);
F(i,1,n)
{
d[1][i] = cost[1][i];
s[1][i] = 0;
}
F(i,2,m)
{
s[i][n+1] = n;
for(int j=n;j>i;--j)
{
F(k,s[i-1][j],s[i][j+1])
{
if(d[i][j] > d[i-1][k] + cost[k+1][j])
{
d[i][j] = d[i-1][k] + cost[k+1][j];
s[i][j] = k;
}
}
}
}