CF605E Intergalaxy Trips 题解

Description

• $n$ 个点的有向完全图。
• $i \to j$ 的边每天出现的概率均为 $p_{i,j}$，若 $i = j$，有 $p_{i,j} = 1$。
• 每天可以选择一条存在的出边走过去或停留在原地不动。
• 求最优策略下从 $1$ 到 $n$ 的期望天数。
• $n \le 10^3$。

Solution

设 $f_i$ 表示 $i$ 到 $n$ 的期望天数。

假设 $f$ 已经求出，那么 $i$ 每次走到的下一步 $j$ 一定是满足 $i\to j$ 这条边出现且 $f_j$ 最小的点。

容易发现如果 $f_j>f_i$ 则 $i$ 下一步无论如何不会走到 $j$。

所以可以得出转移方程：

$$f_i=\sum_{f_j<f_i}p_{i,j}f_j\prod_{f_k<f_j}(1-p_{i,k})+f_i\prod_{f_j<f_i}(1-p_{i,j})+1$$

移项可得：

$$f_i=\frac{\sum_{f_j<f_i}p_{i,j}f_j\prod_{f_k<f_j}{(1-p_{i,k})}}{1-\prod_{f_j<f_i}(1-p_{i,j})}$$

考虑已经确定了前 $k$ 小的 $f$ 值，如何求出第 $k+1$ 小的编号。

注意到只考虑前 $k$ 小的贡献，对于一个没确定的 $i$，再计算一个 $f_j<f_i$ 对 $i$ 贡献后 $f_i$ 一定不会变大，所以如果当前 $f_i<f_j$，则 $i$ 一定不会在 $j$ 后面，否则 $f_i$ 计算 $f_j$ 的贡献后只会更小，与 $i$ 在 $j$ 后矛盾。

所以第 $k+1$ 小的编号就是只考虑前 $k$ 小的贡献的没确定的位置里 $f$ 值最小的编号。

时间复杂度：$O(n^2)$。

Code