洛谷4767 - [IOI2000]邮局

非常简单的四边形不等式优化模板题。

(一)

首先考虑 $O(n^2 \times m)$ 的做法,先将 $a$ 数组排序,假设 $f[i][j]$ 表示前 $i$ 个村庄中设立 $j$ 个邮局,可以列出转移方程:

$$f[i][j] = min(f[i][j], f[k][j - 1] + dis(k + 1, i))$$

其中 $dis(l, r)$ 表示在 $l$ 到 $r$ 的区间中建立一个邮局所对答案产生的贡献,利用人类智慧可知把邮局建在中间花费最少

(二)

在进行四边形不等式优化之前,我们先考虑如何在 $O(1)$ 的时间复杂度内求出 $dis(l, r)$:

在暴力做法中,我们需要枚举 $l$ 到 $r$ 之间的数,去其与中间的村庄的距离差的绝对值,代码大概如下:

1
2
for (int i = l; i <= r; i++)
ans += abs(a[i] - a[mid]);

由于 $a$ 数组是有序的,我们可知在 $mid$ 左面的村庄 $abs(a_i - a_{mid}) = a_{mid} - a_i$,右边的村庄 $abs(a_i - a_{mid}) = a_i - a_{mid}$ 。那么通过前缀和即可在 $O(1)$ 的时间复杂度内求出。

(三)

四边形不等式优化必须满足:

$$f[a][c]+f[b][d]<=f[b][c]+f[a][d]$$

且决策单调。

本题可以通过打表等方法证明成立,那么 $f[i][j]$ 的状态只能从 $f[i][j - 1]$ 到 $f[i + 1][j]$ 的决策中选择一个进行转移。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×