题解 P4767 【[IOI2000]邮局】
andysk
2019-06-12 12:05:40
[Problem](https://www.luogu.org/problemnew/show/P4767)
### 题意
有 $n$ 个村庄，给出了他们的横坐标。现在要在这些村庄中的一些村庄安放 $p$ 个邮局，要求算每个村庄和最近的邮局之间所有距离的最小可能的总和。
### 题解
这个题的 $40\%$ 数据很好写，直接设 $f[i][j] = min\{ f[i - 1[k] + w[k + 1][j] \} \ \ \ \ (k < j)$ , 其中 $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 < k$ 时, 设 $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] \tag{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] \tag{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](k=x)+f[i][j](k=y) \leq f[i][j-1](k=y)+f[i][j](k=x)$
移项可得：$f[i][j-1](k=x)-f[i][j-1](k=y) \leq f[i][j](k=x)-f[i][j](k=y)$
$∵ f[i][j-1](k=y) \leq f[i][j-1](k=x)$
$∴ f[i][j](k=y) \leq f[i][j](k=x)$
则说明对于所有的 $y < x$，一定有 $f[i][j](k=y) \leq f[i][j](k=x)$ ，因此 $f[i][j]$ 的最优决策 $k$ 一定不小于 $y$
对于$K[i][j - 1] \leq K[i][j]$ 方法类似，在此省略
### Code
```cpp
#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;
}
```