ZJOI2010 基站选址 题解

题目链接

dp + 线段树优化。

暴力 dp

• 状态设计：自然想到设 \(f(i, j)\) 表示只考虑前 \(i\) 个村庄，在前 \(i\) 个村庄中建 \(j\) 个基站，并且在第 \(i\) 个存在建立基站时，最小的费用。

• 转移：转移时，枚举上一个建基站的村庄 \(p\)（这同时告诉我们，\(j = 1\) 时要先初始化，否则无法找到上一个建了基站的村庄）：

  \[f(i, j) = c_i + \min_{1 \le p < i} \{f(p, j - 1) + \operatorname{cost}(p, i)\} \]

  其中 \(\operatorname{cost}(p, i)\) 表示在 \(p\) 和 \(i\) 建立基站，而两者之间不建基站的情况下，第 \(p + 1 \sim i - 1\) 个村庄的费用。计算时，要考虑这些村庄是否被基站覆盖，如果被覆盖，则不产生费用，否则第 \(x\) 个村庄产生 \(W_x\) 的费用。

  特别地，当 \(i < j\) 时，\(f(i, j) = +\infty\)，表示无法在前 \(i\) 个村庄中建多于 \(i\) 个基站。

• 初始化：\(f(i, 1)\) 表示只在第 \(i\) 个村庄建基站时，前 \(i\) 个基站的费用。

• 答案统计：我们不知道建几个基站最优，所以对 \(0 \sim k\) 中的所有建基站的数量，我们都拿它更新答案。需要注意，在状态设计中，\(f(i, j)\) 表示只考虑前 \(i\) 个村庄时的答案，这就少考虑了第 \(i + 1 \sim n\) 个村庄的花费。为此有两种解决方法：

  1. 枚举最后一个村庄的位置 \(i\)，统计答案时加上第 \(i + 1 \sim n\) 个村庄的花费。
  2. 假设有一个虚拟的村庄，编号为 \(n + 1\)，两个费用都为 \(0\)，距离为 \(+\infty\)。dp 时，转移到 \(n + 1\)，这样 \(f(n + 1, k + 1)\) 就表示建 \(k\) 个村庄时的总答案。显然这种方法比较简单，这也是 dp 的常用手段：新建一个虚拟的元素，以便统计答案。

转移时，枚举 \(p\)，同时维护 \(\operatorname{cost}(p, i)\)，这样就做到了 \(O(n^2)\) 的时间复杂度。如何动态维护 \(\operatorname{cost}(p, i)\)？不妨假设 \(p\) 从 \(i - 1\) 向左移动，显然一开始没有村庄需要补偿，而随着 \(p\) 向左移动，一些村庄无法被 \(p\) 覆盖，此时就要加上它的贡献。我们可以对每一个村庄 \(x\)，记录它是对于哪些村庄来说，最左边的能覆盖它们的村庄。当 \(p\) 从 \(x\) 移动到 \(x - 1\) 时，就加上这些村庄的补偿费用。

优化

首先，直觉告诉我们，先枚举 \(i\) 再枚举 \(j\) 是没有前途的，因此我们反着来。

考虑用数据结构优化转移时找最小值的过程。一般来说，我们希望把和转移点 \(p\) 相关的值分离出来，也就是把转移方程表示成 \(f(i, j) = g(i) + \min_{1 \le p < i} f(p)\) 的形式。

这里的要点在于把 \(\operatorname{cost}(p, i)\) 表示为只和 \(p\) 有关的量。我自己做这道题时，一直在尝试把这个式子拆开，目的是把 \(p\) 和 \(i\) 分离。这种做法有时是可行的，一段区间的和可以表示成两个前缀和相减。但这道题中的 \(\operatorname{cost}\) 是拆不开的。这里是另一个经典套路：考虑扫描线的思想，把 \(i\) 看作常量。每次 \(i\) 移动时，就更新所有 \(\operatorname{cost}\) 有变化的区间。

具体而言，把 \(f(p, j - 1) + \operatorname{cost}(p, i)\) 看作第 \(p\) 个位置的权值。当 \(i\) 移动到 \(i + 1\) 时，有一部分村庄无法再被 \(i\) 覆盖。如果它同时也不能被 \(p\) 覆盖，那么 \(p\) 的权值就要加上它的补偿费用 \(w\)。

对每个村庄 \(x\)，定义 \(l_x\) 和 \(r_x\) 分别表示最左边和最右边的能覆盖 \(x\) 的村庄。这显然容易用二分求出。对每个 \(i\)，记录有哪些村庄 \(x\) 使得 \(r_x = i\)，设这些村庄构成的集合为 \(S_i\)。\(i\) 移动到 \(i + 1\) 时，对 \(S_i\) 中的所有村庄 \(x\)，使 \(1 \sim l_x - 1\) 的权值加上 \(w_x\)，表示这个范围内的村庄无法覆盖 \(x\)。转移时，取 \(1 \sim i - 1\) 的最小权值加上 \(c_i\) 即可。用线段树维护区间加和区间最小值，时间复杂度 \(O(kn\log n)\)。