【洛谷-P5994】[PA2014]Kuglarz

题意#

有 $n$ 个杯子排成一行，编号为 $1,2,…,n$，其中某些杯子底下藏有一个小球。

对于任意的 $i\leq j$，题目给定 $c_{i, j}$，表示花费 $c_{ij}$ 元，你就可以知道 $i,i+1,…,j$ 底下藏有球的总数的奇偶性。

求至少需要花费多少元，才能保证猜出哪些杯子底下藏着球？

$1\le n\le 2\times 10^3$，$1\le c_{ij}\le 10^9$.

分析#

不能区间DP，时间复杂度都不对。

猜出每个杯子里是否有小球 $\Leftrightarrow$ 知道每个 $[i, i]$ 的奇偶性 $\Leftrightarrow$ 知道每个 $[1, i]$ 的奇偶性。

因为 $i$ 的奇偶性可以通过 $[1, i]-[1, i-1]$ 得到。

花费 $c_{i, j}$ 的代价查询 $[i, j]$ 的奇偶性之后，若我们知道 $[1, i-1]$ 的奇偶性，那么 $[1, j]$ 可以直接计算出。

这并不完全正确，$i=1$ 时，区间 $[1, 0]$ 是不存在的，所以我们把前缀的左端点从 $1$ 改成 $0$。

花费 $c_{i, j}$ 的代价查询 $[i, j]$ 的奇偶性之后，若我们知道 $[0, i-1]$ 的奇偶性，那么 $[0, j]$ 可以直接计算出。

我们在 $i-1$ 和 $j$ 之间连一条权值为 $c_{i, j}$ 的边，表示：在 $[0, i-1]$ 和 $[0, j]$ 二者之中，只要知道一个的奇偶性，花费 $c_{i, j}$ 就可以知道另一个。

那么在这样的图上，$[l, r]$ 连通等价于：已知区间 $[0, l-1]$ 和 $[0, r]$ 的奇偶性。

要选代价一组代价和最小的边，使图连通。

求 $n+1$ 个点的最小生成树即可。

$\rm{Kruscal}$，时间复杂度 $\mathcal{O}(n^2\log n)$.