YbtOJ 454「概率期望 dp」期望旅行

(Updated: )
oi
, , ,

题目链接：YbtOJ #454

小 A 有一张 $n$ 个点的有向图。

已知图中 $x\rightarrow y$ 的有向边每天有 $a_{x,y}$ 的概率存在。保证 $\forall x,a_{x,x}=1$，即所有自环肯定存在。

小 A 从 $1$ 号点出发，每天需要选择当前所在点一条 存在 的出边，走到对应的点。

求采取最优策略时，从 $1$ 号点走到 $n$ 号点的期望天数。

$1\le n\le 3\times10^3$，$0\le a_{i,j}\le 1$

Solution

设 $E(x)$ 表示 采取最优策略时，从 $x$ 走到 $n$ 的期望步数。

假设对于一个点 $x$，已知有 $k$ 个点 $y_1,y_2,…,y_k$ 满足 $E(y_1)\le E(y_2)\le…\le E(y_k)\le E(x)$。

显然贪心地去考虑，必然是尽可能走到 $y_1$，次优是走到 $y_2$，以此类推。

所以我们可以倒着做，记 $s_x=\sum_{i=1}^k(E(y_i)+1)\times a_{x,y_i}\times\prod_{j=1}^{i-1}(1-a_{x,y_j})$，表示 离开 $x$ 到 $n$ 的期望天数。

记 $p_x=\prod_ik(1-a_{x,y_i})$，表示 不会离开 $x$ 的概率。

那么 $E(x)$ 的计算就很简单了，只需分是否离开两种情况，得到 $E(x)=p_x(E(x)+1)+s_x$，化简即 $E(x)=\frac{s_x+p_x}{1-p_x}$。

直接暴力类似 Dijkstra 转移即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
Cn int N=3e3+10;
int n,vis[N];
double a[N][N],s[N],e[N],E[N];
int main(){
    freopen("trip.in","r",stdin),freopen("trip.out","w",stdout);
    RI i,j,u;for(scanf("%d",&n),i=1;i<=n;i++) for(j=1;j<=n;j++) scanf("%lf",&a[i][j]);
    auto CL=[&]() -> void{RI i;for(i=1;i<=n;i++) !vis[i]&&(e[i]=0.0,s[i]=1.0);};
    auto CT=[&](CI x) -> void{RI i;for(i=1;i<=n;i++) !vis[i]&&(e[i]+=(E[x]+1)*a[i][x]*s[i],s[i]*=1.0-a[i][x]);};
    auto CP=[&]() -> void{RI i;for(E[u=0]=2e9,i=1;i<=n;i++) !vis[i]&&(E[i]=(s[i]+e[i])/(1.0-s[i]),E[i]<E[u]&&(u=i));};
    CL(),u=n;W(u) vis[u]=1,CT(u),CP();return printf("%.8lf\n",E[1]),0;
}