IOI2000 Post Office (POJ1160)

前言

昨天XY讲课！讲到这题！还是IOI的题！不过据说00年的时候DP还不流行。

题面

http://poj.org/problem?id=1160

分析

§ 1 中位数

首先我们考虑，若有x₁ < x₂ < ... < x_n，则当∑abs(x - x_i)最小时，x为x₁, x₂, ... , x_n这n个数的中位数。

证明如下：我们把x₁, x₂, ... , x_n看作数轴上n个点，我们先考虑两端，要使abs(x - x₁) + abs(x - x_n)最小，那么x必定在x₁和x_n中间，这是个很显然的初中数学题。

好，那么我们就可以置这两个点不管了；剩下的点我们也这样考虑，如此类推，最后要么剩下一个点，要么就是剩下两个点中间的一段区间，答案就显而易见了。证毕。

（在July 1, 2018的AtCoder Contest 100 Task C Linear Approximation就是用这个思路，但是不知道为什么到比赛结束我还是WA，到时候也搞个这题的题解）

§ 2 给定一段村庄怎么放邮局

我们要求每个村庄到邮局距离总和最近，那么给定一段区间里的村庄，我们要找到一个满足要求的村庄建邮局，由上面关于中位数的结论可知，建邮局的村庄就是这段村庄最中间的那个。

§ 3 动态规划

既然我们知道，在一段给定的村庄下放邮局的最小花费，那么很容易想到一个区间DP的思路。

设DP[i][j]表示在编号为1~i的村庄中，建了j个邮局，所需的最小花费。

这时转移方程已经非常明显了：

DP[i][j] = min{ DP[k][j - 1] + cost[k + 1][i] }

其中j - 1 <= k <= i，cost[l][r]表示在l到r的区间里建一个邮局所需花费。

而cost是可以在O(n²)的时间内预处理出来的，那么时限是绝对绰绰有余了。

参考代码

 1 // POJ1160
 2 // IOI2000
 3 // Post Office
 4 #include <cstdio>
 5 #include <algorithm>
 6 const int MAXV = 305, MAXP = 35, INF = 0x3f3f3f3f;
 7 
 8 int V, P, X[MAXV], DP[MAXV][MAXP], sum[MAXV][MAXV];
 9 
10 int main() {
11     scanf("%d%d", &V, &P);
12     int i, j, k, lim;
13     for (i = 1; i <= V; i++) scanf("%d", &X[i]);
14     for (i = 1; i < V; i++)
15         for (j = i + 1; j <= V; j++) sum[i][j] = sum[i][j - 1] + X[j] - X[i + j >> 1];　　// 预处理cost，这里用sum写了
16 //    DP[0][0] = INF;　　// 这里注意DP[0][0]=0，但是DP[i][0]=INF，当i > 0时，因为这时候这个状态是没有意义的
17     for (i = 1; i <= V; i++) {
18         DP[i][0] = INF;
19         lim = std::min(i, P);
20         for (j = 1; j <= lim; j++) {
21             DP[i][j] = INF;
22             for (k = j - 1; k < i; k++) DP[i][j] = std::min(DP[i][j], DP[k][j - 1] + sum[k + 1][i]);
23         }
24     }
25     printf("%d
", DP[V][P]);
26     return 0;
27 }

总结

如果放在现在，这大概就够个联赛题难度了。但是当年呢DP在算法竞赛中还不常用，所以当年要想到这个思路，是非常不容易了。

附

讲题是zzd大佬还讲了一个很奇怪的方程：

DP[i][j]表示前i个村庄，建了j个邮局，其中第i个村庄一定是邮局的最小花费。

当然这个状态转移也不难写，但是要注意答案不是DP[V][P]，而是DP[V + 1][P + 1]。（即加一个假村庄，假村庄上建一个假邮局，这样就会把前面n个村庄的花费也正常纳入了，当然要通过一些手段不计算假村庄的花费）