[IOI 2000]邮局

Description

题库链接

给你 \(n\) 个村庄，你需要在这 \(n\) 个村庄中选出 \(m\) 个建邮局。要使得每个村庄到最近的邮局距离和最小。

\(1\leq n\leq 3000,1\leq m\leq 300\)

Solution

记 \(f_{i,j}\) 表示前 \(i\) 个村庄建 \(j\) 个邮局最少的距离和。那么 \(f_{i,j}=\min\{f_{k,j-1}+w(k+1,i)\}\)，其中 \(w\) 表示这区间内的村庄建一个邮局的距离和。这是可以 \(O(1)\) 算出的。

于是我们考虑一下这个 \(f\) 的性质，令 \(i\leq i',j\leq j'\)，那么有 \(f_{i,j'}+f_{i',j}\geq f_{i,j}+f_{i',j'}\)。这个感性理解一下就是较多的邮局建到较少的村庄中一定比建到较多的村庄中浪费。

因此我们的 \(f\) 是满足四边形不等式的。因此记 \(s_{i,j}\) 表示 \(f_{i,j}\) 的最优决策点，那么是可以用四边形不等式定理优化的，具体可以参考这篇文章。

将枚举区间变成 \(s_{i,j-1}\leq k\leq s_{i+1,j}\)，那么复杂度为 \(O(n^2)\)。

Code

#include 
using namespace std;
const int N = 3000+5;

int n, m, x[N], f[N][305], s[N][305];

int w(int l, int r) {
    int mid = (l+r)>>1;
    if ((l+r)&1) return x[r]-x[mid]*2+x[l-1];
    else return x[r]-x[mid]-x[mid-1]+x[l-1];
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &x[i]);
    sort(x+1, x+n+1);
    for (int i = 1; i <= n; i++) x[i] += x[i-1], f[i][1] = w(1, i);
    for (int i = 1; i <= m; i++) s[n+1][i] = n;
    for (int j = 2; j <= m; j++)
        for (int i = n; i >= 1; i--) {
            f[i][j] = ~0u>>1;
            for (int k = s[i][j-1]; k <= s[i+1][j]; k++) 
                if (f[k][j-1]+w(k+1, i) < f[i][j])
                    f[i][j] = f[k][j-1]+w(k+1, i), s[i][j] = k;
        }
    printf("%d\n", f[n][m]);
    return 0;
}