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

(一)

首先考虑 $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]$ 的决策中选择一个进行转移。

(四)

代码:

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
// ==============================
// author: memset0
// website: https://memset0.cn
// ==============================
#include <bits/stdc++.h>
#define ll long long
using namespace std;

int read() {
int x = 0; bool m = 0; char c = getchar();
while (!isdigit(c) && c != '-') c = getchar();
if (c == '-') m = 1, c = getchar();
while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
if (m) return -x; else return x;
}

const int maxn = 3010, maxm = 310;
int n, m;
int a[maxn];
int s[maxn][maxn];
int f[maxn][maxn];
int dis[maxn][maxn];
int tran[maxn][maxn];

int main() {

memset(f, 0x3f, sizeof(f));

n = read(), m = read();
for (int i = 1; i <= n; i++)
a[i] = read();
sort(a + 1, a + n + 1);

for (int i = 1; i <= n; i++)
for (int j = i; j <= n; j++)
s[i][j] = s[i][j - 1] + a[j];

for (int l = 1; l <= n; l++)
for (int r = l; r <= n; r++) {
int mid = (l + r) >> 1;
dis[l][r] += (mid - l) * a[mid] - s[l][mid - 1];
dis[l][r] += s[mid + 1][r] - (r - mid) * a[mid];
}

for (int i = 1; i <= n; i++)
f[i][1] = dis[1][i];
for (int j = 2; j <= m; j++) {
tran[n + 1][j] = n;
for (int i = n; i >= 1; i--) {
for (int k = tran[i][j - 1]; k <= tran[i + 1][j]; k++)
if (f[k][j - 1] + dis[k + 1][i] < f[i][j]) {
f[i][j] = f[k][j - 1] + dis[k + 1][i];
tran[i][j] = k;
}
}
}

printf("%d\n", f[n][m]);

return 0;
}