P4360 [CEOI2004] 锯木厂选址 题解

· · 题解

设 f_{k, i} 表示在点 i 设置第 k 个锯木厂的最小代价，那么有：

f_{k, i} = \min\limits_{j < i}\left(f_{k - 1, j} + w\left(j + 1, i\right)\right)

其中 w\left(i, j\right) 表示区间 \left[i, j\right] 的木材运送至点 j 的代价。下面证明其满足四边形不等式。

首先，w\left(l, r\right) 满足四边形不等式，当且仅当：

w\left(l, r\right) + w\left(l + 1, r - 1\right) \ge w\left(l + 1, r\right) + w\left(l, r - 1\right)

移项可得：

w\left(l, r\right) - w\left(l + 1, r\right) \ge w\left(l, r - 1\right) - w\left(l + 1, r - 1\right)

即 f_l\left(r\right) = w\left(l, r\right) - w\left(l + 1, r\right) 随 r 的增长单调不减，不难发现 f_l\left(r\right) 可以表示为将点 l 的木材运送至点 r 的代价，由于距离和代价均为非负整数，因此 f_l\left(r\right) 单调不减，即 w\left(l, r\right) 满足四边形不等式。

进而可以推知 f_{k, i} 满足决策单调性，因此使用分治优化转移即可。

复杂度为 O\left(nk\log n\right)，其中 k = 3。