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

yzxoi

发布于 2022-09-19 13:44:24

5270

发布于 2022-09-19 13:44:24

文章被收录于专栏：OI

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

题目链接：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

#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;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-02-06 ，如有侵权请联系 cloudcommunity@tencent.com 删除

dijkstra