沙雕网友的博客

CF605E Intergalaxy Trips 题解

2021-09-30 15:41:42


CF605E Intergalaxy Trips 题解

期望好题(确信)

总之就是,期望做得太少,人太菜,一上午做不出来。

题意不再赘述啦

CF605E Intergalaxy Trips

朴素分析

首先有个思路,如果我们设 $f_i$ 为 $i\to n$ 的期望耗时,那么当我们转移时,我们一定不会找比当前点更劣的点转移。因为那样就是跑个自环也比跑那个劣的点划算,所以转移的时候只考虑比当前点优的点即可。

问题是自己不知道,别的也不知道,怎么判断?这个就要看转移方程了。

状态转移

因为会选择最优策略,所以到了某个点,采取某个状态的唯一可能就是比自己优的状态取不到了,这个东西是可以描述出来的。而且如果所有状态都取不到那就自环,这是最劣的转移,不过也要考虑。于是我们的转移方程:$$ f_i=\sum_{j}^{f_j<f_i}p_{i,j}f_j\prod_k^{f_k<f_j}(1-p_{i,k})+f_i\prod_{j}^{f_j<f_i}(1-p_{i,j})+1 $$ 移项然后除一下可以得到:$$ f_i=\frac{\sum_{j}^{f_j<f_i}p_{i,j}f_j\prod_k^{f_k<f_j}(1-p_{i,k})+1}{1-\prod_{j}^{f_j<f_i}(1-p_{i,j})} $$

实现思路

首先,对于上式中的更新 $i$ 的 $j$,显然是考虑的越多值是单调不增的,不然你也不会用那个点去转移。然后注意,一个点是不可能比将它转移的点更优的,因为要多走一步。

这说明了什么?当一个点是所有已知状态中最小的,那么它就不会再被别的状态转移了,这个性质很类似 Dijkstra ,所以我们可以每一轮选择最小的那个没有进行过转移的点,将其它没有进行过转移的点更新一下,类似朴素的 $O(n^2)$ 的 Dijkstra ,这样我们就能得到答案。

注意这里“转移”指的是用当前点去更新别的点的答案,即对于别的点 $i$ 来说,它相当于公式里面的 $j$。

实现细节

我们可以分别维护每个点的 $f_i,g_i,h_i$,$f_i$ 与上文含义相同,三者关系可表示为:$$ f_i=\frac{g_i}{1-h_i} $$ 而且更有趣的是,当我们用 $j$ 更新 $i$ 时(注意不是任意时刻),还没被 $j$ 更新过的 $h_i$ 恰好等于 $\prod_k^{f_k<f_j}(1-p_{i,k})$,也就是每一轮更新我们可以这么写:

$g_i+=p_{i,j}f_jh_i$,$h_i*=1-p_{i,j}$,$f_i=\frac{g_i}{1-h_i}$

要注意转移顺序。

贴代码

#include <bits/stdc++.h>
#define lint long long
#define rint register int
using namespace std;
inline int read(){
    char c;int f=1,res=0;
    while(c=getchar(),!isdigit(c))if(c=='-')f*=-1;
    while(isdigit(c))res=res*10+c-'0',c=getchar();
    return res*f;
}
const int N=1e3+5,inf=1e9;
double p[N][N],f[N],g[N],h[N];
//最后的f才是答案,其为g/(1-h) 
int q[N],tot,n;//q实质上是拓扑序排列
bool vis[N];//判断是否在队列里面 
inline void upd(){//用队头来更新 
    int j=q[tot];
    for(rint i=1;i<=n;++i){
        if(vis[i])continue;
        g[i]+=f[j]*p[i][j]*h[i];
        h[i]*=1-p[i][j];
        f[i]=g[i]/(1-h[i]);
    }
}
inline void solve(){
    for(rint i=1;i<n;++i)
        f[i]=g[i]=h[i]=1;
    f[n]=0;h[n]=1;
    //恰好都是1 
    vis[n]=true;
    q[++tot]=n;upd();
    while(tot<n){
        int id;double v=inf;
        for(rint i=1;i<=n;++i)
            if(!vis[i]&&f[i]<v)
                v=f[i],id=i;
        vis[id]=true;
        q[++tot]=id;upd();
    }
}
int main(){
    n=read();
    if(n==1){return puts("0"),0;}
    for(rint i=1;i<=n;++i)
        for(rint j=1;j<=n;++j)
            p[i][j]=read()/100.0;
    solve();
    printf("%.8lf",f[1]);
    return 0;
}