非常荣幸今年能够有机会为这样一个大规模的程序设计竞赛出题，在全国为数众多的OIers和ACMers面前献丑，也实属鼓足了勇气，万幸的是整个比赛比较平静，看各个论坛和群也没有人指责我题目的问题，算是得到了些许安慰。

我计划本篇报告一共分成三次来写，第一和二部分分别是B和C的详细算法，第三部分是我关于这次题目在出题过程中的一个简单总结，或者叫花絮，希望愿意读的朋友来捧场。

好了，先来看看题目。B题的原文描述如下：

现在，麻烦来了，T公司要在全国n（1<=n<=10,000）个城市中架设服务器，以提高其网络服务质量。但由于资金限制，我们只能选择其中P（1<=p<=50且p<=n）个城市作为服务中心，其余的城市需要由这P个城市中的一个来提供服务。如何选择这P个城市并提高通讯质量难倒了一批又一批的工程师。
好在，传闻Richard是这方面的专家，于是T特聘他来帮忙解决问题。果然，Richard到了公司后就开始大展拳脚。首先，对于城市A，如何快速的求出应该把哪个城市的服务器分配给它？这个问题至关重要，因为用户并不希望等待过长时间才开始使用服务。
你的方法是通过考虑每个城市服务器的特点，然后将每个城市表示为一个整数（32位有符号整数范围）。对于城市A，我们表示为network(A)。那么，谁来为A提供服务？令对任意城市x，value(A)=abs(network(x)-network(A))（其中abs为取绝对值），那么，我们说为A提供服务的城市应该是使得value(A)最小的一个（如果有多个，则任意选一个）。这一步处理工作完毕后，剩下的工作是如何找到这P个安放服务器的城市。为了达到最好的服务质量，这样的安排需要满足所有城市的value总和最小。
这个问题难倒了Richard。为了拿到工钱（更重要的是保住其专家的称号），他决定不惜重金悬赏求解这个问题。聪明的你，还不快来试试？

其实这就是IOI2000经典问题Post Office的升级版。很多人可能都看过毛子青的那篇经典的将动态规划优化的论文，但惟独一个遗憾是他那篇文章在分析用四边形不等式优化该问题时最后得到的复杂度结论有错，那个算法应该是O(n^2)的复杂度而非O(np)，这也是为什么很多人吃了TLE的原因。

其实，更早有一篇IOI集训队论文就已经讲到了一个非常优美的算法，不过那篇文章非常简短，所以很多人可能没有在意。我标程的算法其实就是那个，在这篇报告中我稍微详细的讲讲。

首先对所有数据进行排序，这步证明很基本，反证得之，略过。然后列出基本的DP方程：f(k, j) = f(k-1, i-1) + W(i, j)。其中，f(k,j)表示从前j个城市中选择k个作为服务中心的最小开销，W(i,j)表示从数据排行第i的城市至第j的城市中选取一个作为服务中心的最小代价。假设排序后的数据存放在X中。

下面首先证明一个性质：使得W(i,j)最小的城市一定是第(i+j)/2个。假设P(k)表示选取第k个城市作为中心，如果k < (i+j)/2，那么有：

P(k+1) = P(k) + (k+1-i)*( X(k+1) – X(k) ) – (j-k)*( X(k+1) – X(k) )

= P(k) + (k*2+1-i-j)*( X(k+1) – X(k) )

因为 k < (i+j)/2，所以有k ≤ (i+j)/2 – 1，就有(k*2+1-i-j) < 0。因此得到P(k+1) < P(k)。同理，当k > (i+j)/2时也可以如法炮制的证明。于是原命题得证。

接着我们来回顾一下所谓的Convex Monge Condition，也就是常说的四边形不等式。仍然用上面的W来描述，就是：

W(a,c) + W(b,d) ≤ W(b,c) + W(a,d)，对所有的a < b 且 c < d成立。

接着介绍的另外一个很类似的概念：Convex Totally Monotone，中文叫凸完全单调性。定义如下：

W(a,c) ≥ W(b,c) => W(a,d) ≥ W(b,d)，对所有的a < b且c < d都成立，其中=>是逻辑蕴含的意思。

这个东西有什么神奇的性质呢？来看两个：

1. 假设W是个n行m列的矩阵（以后都这么说），设Ri表示第i列的所有元素的最小值所在的行。那么有R1<=R2<=R3…<=Rm；

2. 四边形不等式能推导出凸完全单调性，但是反之则不然。

我现在要说是，这个题目中的W满足这个凸完全单调性吗？或者更甚，满足四边形不等式吗？这两个问题的答案都是肯定的。那么如何证明呢？因为后一个命题的更强，所以我们只需要证明满足四边形不等式就好，可以通过两步证明：

1. 对所有的i ≤ p ≤ j，有W(i, j+1)-W(i, j) ≥ W(p, j+1)-W(p, j)。

2. 将上式中的i和p替换为a和b，然后将j替换为所有区间[c,d]间的数，于是得到d-c+1个不等式，把它们加起来就可以得到答案。

下面就利用这个性质来设计高效算法。

回顾刚才的基本方程：f(k, j) = f(k-1, i-1) + W(i, j)。当k固定的时候，我们需要枚举i和j，在naïve算法中这是个O(n^2)的过程。假设矩阵B(i, j) = f(k-1, i-1) + W(i, j)，其中k ≤ i ≤ j，那f(k, j)其实就是B的第j列的最小元。因此，我们的目标就是加快求出B的所有列的最小元。

首先可以证明，当W满足四边形不等式时，B也满足。自然，B也同时满足凸完全单调性。我们用一个三元组（start, end, r）表示在[start, end]间的所有列的最小元在第r行上。算法开始时，我们只有一个元组(k, n, k)，即当我们只考虑了第k行的元素时，所有列的最小元都在第k行。接下来我们一次考虑第k+1, k+2……行。设当前考虑第p行，那么我们的工作就是在最快的时间内找到一个t，当所关心的列 ≥ t时，我们有他们第最小元在第p行。

首先，我们用一个队列维持当前的所有元组，并且满足下一个元组的start是上一个的end+1，即列的区间维持一个升序。然后初始化t = n+1，然后从最后一个元组开始考虑，那么只有三种情况：

1. 当B(end, p) ≥ B(end, r)时，我们知道对所有的c < end，有B(c, p) ≥ B(c, r)。这个就是凸单调性的逆否命题。这时我们不需要再向前扫描了；

2. 当B(start, r) ≥ B(start, p)时，根据凸单调性，对所有的c > start，有B(c, r) ≥ B(c, p)。这时我们知道该元组已经作废了，因为[star, end]中的所有列的最小元都不在r，至少有p就比它们小。于是弹出改元组，继续向前扫描；

3. 第三种情况就是，在[start, end]中存在一个t，使得对所有c ≥ t，有B(c, r) ≥ B(c, p)。如何来找这个t呢？通过二分查找就可以轻松的确定。这时也不需要再继续向前扫描。

然后我们就得到了这么一个t。如果t < n + 1的话，我们就加入一个元组( t, n, p)，否则就什么都不干。当最后一行n都计算完毕后，此时我们在队列中就维护者我们之前想要计算的答案：对于B的每一列，它的最小元在哪一行。

通过均摊分析，我们发现整个计算过程是O(nlgn)的复杂度。当然，B一共需要求P次，所以总的复杂度是O(Pnlgn)。

具体实现还是有好多需要考虑的细节，大家自由发挥。如果愿意的话，可以向我提出挑战我的程序（如果你有更好的算法，希望你能告诉我，因为我知道传说中好像真的有一个O(nP)的算法存在，只是我能力有限未能搞明白），然后咱们一边去晒晒，^_^。

这篇就到此为止，本题的数据和参考代码可以跟我发邮件（[email protected]）索取。下一篇讲C 题。说实话，其实我更喜欢C一些，因为solution所需要的知识非常简单，只是中间的模型变化不容易想到，而B是如果没学过相关知识，从头到尾都不容易想。貌似比赛中C没有被人做掉，这点我还是有一些遗憾，希望大家能再想想。

先离题，我觉得有必要先定义难和易的概念。

有些题目，它可能要经过好几步的模型转换，而且每一步的处理都需要一些比较高深的算法，比如网络流，自动机等。但是，其中的每一步的转化非常的straight forward，或者说用一些很普通的处理手段就可以看出解决方法。这类的题目非常多，特别是POJ月赛中。但我认为它们并不能算真正意义上的难题，能够做出不值得骄傲。

还有些问题，可能解决方法非常简单，代码量也非常小，但是却需要打破常规思路才能得到答案。我觉得就是要做这类题目，才可能在思维上有质的飞跃。

最近的两场SRM（423和424）就出现了两道我觉得值得一提的题目，下面介绍一下。

第一道题目是300pts。一个无限大的棋盘上放了n (n<=50) 个棋子，初始是任意的放置，所以也可能有位置相同的。问题是，最少移动多少步可以使得至少K个棋子在同一个位置上？其中从A移动到B的步数是两者的曼哈顿距离。

有一个很简单的问题我们或许都知道其答案：将n个棋子放在一起最少需要多少步移动？由于曼哈顿距离的特点，我们可以分开算X坐标和Y坐标。最后所有棋子移动到的点的X坐标一定是它们初始坐标排序后的中位数，Y坐标同理。因此，我们可以在O(n)的时间内解决将所有棋子移动到一起的问题。

现在考虑K<n。显然，普通的做法就是在n个中枚举K个棋子，然后用上面的方法计算移动步数。这样做的复杂度是O(C(n,k)*n)，显然不能接受。那么，如何优化？其实很简单，就是将这个不可接受的算法的计算顺序颠倒一下。仔细想想，由于X和Y坐标都是取中位数，也就是说最终要移动到的位置的X和Y的坐标是可以从已知的这n个点中组合出来的！因此，n个点最多有n^2个候选的位置，而对于选出的目标位置，很显然就是是n个点中离它最近的K个移动到一起。因此，通过简单的调换计算顺序避免了大量重复计算，将复杂度降为O(n^2KlgK)。

其实，这个算法也体现了动态规划思想的精髓：避免重复计算。然而，上面看似简单的算法，却非常不容易想到，原因就是我们先入为主的思想在作祟。

另外一个是600pts的题目。你在玩一个冒险游戏，现在有n个关卡。要通过一个关卡，玩家的当前智商和力量的值至少有一个要大于等于该关卡的限制。每通过一关，可以得到一些分数，你可以将这些分数任意的分配到你的智商和力量的属性上。初始你的智商和力量都为1，请问，如果通关的顺序没有要求，请问你最多能通过多少关？其中，关卡的属性值限制<=1000，n<=50。

初看真没什么想法，那就枚举吧。先枚举出通关的顺序，然后再求解这个顺序下最多能通多少关，复杂度是O(n!*n)。想基于这个思路动规，好啊，那总得状态压缩一下吧，答案是O(1000*1000*n*2^n)，没觉得这个方法有多好，怎么办？

其实，第一题的优化已经提示我们，盲目的枚举必然隐藏了大量的重复计算。回顾一下，第一题的重复计算在哪里？其实就在于，虽然一共有C(n,K)种点的组合，但是它们却一共只有O(n^2)中不同的最终集合位置。形式化一点，就是这指数阶的组合方案它们的某一个性质一共只有多项式阶种。回到这道题，其实就是所有通关顺序得到的最后的智商和力量属性的组合最多只有1000^2种（去掉>1000的情况，因为1000已经是所有关卡要求的上限）！

那么依葫芦画瓢，先枚举一种属性组合，然后再求出能得到这个属性组合的最优通关序列。很快发现，这样的话，不直接枚举(1000,1000)就可以通过所有关卡了？所以，再这一思路上，我们还应该多做些限制才好。

那么，为什么不能枚举(1000,1000)呢？原因就是这个组合或许根本就不存在。而题目一中不做这个处理的原因是，虽然有些位置不可能作为最终位置，但是计算它们不会影响最后答案。那如何快速判断哪些状态是可能出现的呢？

设状态(x,y)是可达的，则(x,y)必然是由某一个可达状态(x’,y’)通关后得到P分生成的（注意，假设P可以不用全部分配。因为这一假设不影响最后的答案，所以它是可行假设）。因此，很容易想到可以通过广度优先的过程从(1,1)开始，每次检测该状态能通过的所有关卡能得到的总分数，然后把剩余分数，即left=y+x-2分配后求得其它的可行状态。

答案很明显了，不再多说。

再总结一下这两道题目的特点。它们将一个具有指数阶以上定义域的问题转化到只有多项式阶的状态空间中，再在此状态空间中设计算法以得到原问题的最优解。我们可以看到，上面的算法的都不难证明，而且代码也容易写就，难就难在如何转化问题的状态空间。我觉得，只有多做这样的题目，才能迅速成长。

最后，即使你实现上面的算法很容易，也请抽空看看楼教主的代码，非常漂亮。