Luogu4767 [IOI2000]邮局

Problem

题意

​ 有 n 个村庄，给出了他们的横坐标。现在要在这些村庄中的一些村庄安放 p 个邮局，要求算每个村庄和最近的邮局之间所有距离的最小可能的总和。

题解

​ 这个题的 40\% 数据很好写，直接设 f[i][j] = min{ f[i - 1[k] + w[k + 1][j]}\ \ \ \ (k , 其中 w[i][j] 表示一个邮局覆盖的 [i,j] 村庄之间的距离。

​ 再考虑 100\% 的数据，可以用四边形不等式优化。现在开始证明四边形不等式对二维区间DP成立。则可先证明 w 为凸。

​ 当 w 为凸时，当且仅当 w[i][j] + w[i + 1][j + 1] \leq w[i][j + 1] + w[i + 1][j]，那么需要有：w[i + 1][j] - w[i][j] 关于 j （非严格）递减。

​ 再证明 f 为凸时，根据上面的结论，则需证明： f[i][j] + f[i + 1][j + 1] \leq f[i][j + 1] + f[i + 1][j]

​ 假设四边形不等式对该式成立，并且 j - i 时, 设 f[i][j + 1] 的最有决策（最优解）k = x ，f[i + 1][j] 的最优决策是 f[i+1][j] = y 。不妨设 i + 1 \leq x \leq y，此时因为 x,y 都是最优决策，根据以上结论，有：f[i][j + 1] + f[i + 1][j] = f[i][x] + f[x + 1][j + 1] + w[i][j + 1] + f[i + 1][y] + f[y + 1][j] + w[i + 1]\ \ \ \ \ (1)

​ 若要使 i + 1\leq y \leq x，则可以先分别写出 f[i + 1][j] 和 f[i][j + 1] 的等价式子（用含有w[i][j]的式子表示），再对他们套用公式进行合并。之后与上式进行分类讨论。

​ 即使 x,y 不是最优解，我们仍有：f[i][j] + f[i + 1][j + 1] \leq f[i][x] + f[x + 1][j] +w[i][j] + f[i + 1][y] + f[y +1][j + 1] + w[i + 1][j + 1] \ \ \ \ (2)

​ 根据以上归纳假设，得：f[x + 1][j] + f[y + 1][j + 1] \leq f[x + 1][j + 1]+ f[y + 1][j]

​ 比较 (1) (2) 两式，可得 f[i][j] + f[i + 1][j + 1] \leq f[i][j + 1] + f[i + 1][j]

​ 证毕。

​ 最后证明 K[i][j - 1] \leq K[i][j] \leq K[i+1][j]

​ 证明 K[i][j - 1] \leq K[i][j] 时，先假设 f[i][j -1] 有最优决策 k = y ，再根据 x \leq y\leq j-1<j ，列出四边形不等式：f[i][y] + f[i + 1][k] \geq f[i][k] + f[i + 1][y]

​ 在不等式两边添加一定的项试图得到 f[i][j-1]+f[i][j] \leq f[i][j-1]+f[i][j]

​ 移项可得：f[i][j-1]-f[i][j-1] \leq f[i][j]-f[i][j]

​ ∵ f[i][j-1] \leq f[i][j-1]

​ ∴ f[i][j] \leq f[i][j]

​ 则说明对于所有的 y，一定有 f[i][j] \leq f[i][j] ，因此 f[i][j] 的最优决策 k 一定不小于 y

​ 对于K[i][j - 1] \leq K[i][j] 方法类似，在此省略

Code

#include <bits/stdc++.h>
using namespace std;

const int SIZE = 3000 + 5;
const int inf = 0x7f7f7f7f;

int n, p;
int a[SIZE], sum[SIZE], f[SIZE][SIZE], k[SIZE][SIZE];

inline int read()
{
    char ch = getchar();
    int f = 1, x = 0;
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
    return x * f;
}

inline int Calc(int x, int y)
{
    int Mid = (x + y) >> 1;
    return sum[y] - sum[Mid] - (y - Mid) * a[Mid] + (Mid - x) * a[Mid] - sum[Mid - 1] + sum[x - 1];
}

int main()
{
    n = read(), p = read();
    for (int i = 1; i <= n; i++)
    {
    a[i] = read();
    sum[i] = sum[i - 1] + a[i];
    }
    for (int i = 0; i <= n; i++)
    f[i][i] = 0, k[i][i] = i;
    for (int len = 1; len <= n - p; len++)
    {
    int j = 0;
    for (int i = 0; (j = i + len) <= n; i++)
        f[i][j] = inf;
    for (int i = 1; (j = i + len) <= n; i++)
    {
        for (int K = k[i][j - 1]; K <= k[i + 1][j]; K++)
        {
        int t = f[i - 1][K - 1] + Calc(K, j);
        if (t < f[i][j])
        {
            f[i][j] = t;
            k[i][j] = K;
        }
        }
    }
    }
    printf("%d", f[p][n]);
    return 0;
}