【Codeforces 605E】Intergalaxy Trips

mrsrz 1月 03, 2020

期望dp，贪心。

题目大意：

给定一张有向图，每天每条边都有一定概率出现。

从 $1$ 出发要走到 $n$，每天可以走一条出现的边或者原地不动。

求最优策略下走到 $n$ 的期望天数。

题解：

类似 Dijkstra 最短路算法的贪心思路。

令 $f_i$ 表示从 $i$ 走到 $n$ 的期望天数。

假设我们当前已经确定期望的点的序列按期望从小到大排序后为 $a_1,a_2,\ldots,a_k$，那么我们每次只从 $a$ 中的点转移。

从这些集合进行转移得到的其他点的期望步数中，我们取期望最小的那个插入 $a$ 的最后面。

期望小的点显然不会从其他期望大的点转移过来，而期望大的点可能从期望小的点转移过来。我们每次取的是当前集合转移到的期望最小的点，那么这个点的最小期望就是计算出来的值。

考虑如何计算这个期望。

我们显然直接走到期望尽可能小的点，因此：

$f_x=1+\sum_{i=1}^k f_{a_i}\times p_{x,a_i}\times (\prod_{j=1}^{i-1}1-p_{x,a_j})+f_x\times \prod_{i=1}^k 1-p_{x,a_i}\\ f_x=\frac{1+\sum_{i=1}^k f_{a_i}\times p_{x,a_i}\times (\prod_{j=1}^{i-1}1-p_{x,a_j})}{1-\prod_{i=1}^k 1-p_{x,a_i}}$

这些信息每次从上一轮计算的结果继承下来继续计算即可。

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

Code：

#include<cstdio>
const int N=1e3+6;
double P[N][N],f[N],E[N],p[N];
bool vis[N];
int n;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    for(int j=1,k;j<=n;++j)scanf("%d",&k),P[i][j]=k/100.;
    f[n]=0;
    vis[n]=1;
    for(int i=1;i<n;++i)p[i]=1-P[i][n],E[i]=1;
    for(int T=1;T<n;++T){
        int u=0;double ff=1e18;
        for(int i=1;i<n;++i)if(!vis[i]){
            double g=E[i]/(1-p[i]);
            if(g<ff)u=i,ff=g;
        }
        f[u]=ff,vis[u]=1;
        for(int i=1;i<n;++i)if(!vis[i])
        E[i]=E[i]+p[i]*P[i][u]*ff,p[i]*=1-P[i][u];
    }
    printf("%.100f\n",f[1]);
    return 0;
}