正题

题目链接:https://www.luogu.com.cn/problem/CF605E

题目大意

给出\(n\)个点的一张完全有向图，每一天\(i\)到\(j\)的路径有\(p_{i,j}\)的概率出现。

询问从\(1\)出发走到\(n\)在最优策略下的期望天数。

\(1\leq n\leq 10^3,p_{i,i}=1\)

解题思路

设\(g_i\)表示从\(i\)到\(n\)的答案，那么\(g\)满足式子

\[g_i=\sum_{j=1}^{n}\frac{g_{j}}{\prod_{g_k<g_j}(1-p_{j,k})}\times p_{i,j}\times \prod_{g_k<g_j}(1-p_{i,k})
\]

注意到里面有条件\(g_k<g_j\)，但是我们并不知道\(g\)，好像就死循环了。

但是我们可以知道\(g_n\)肯定是最小的而且是\(0\)，然后剩下第二小的只会受到\(g_n\)的影响，也就是这个里面有一个的\(g\)是完整的。

可以猜测这个第二小的肯定是剩下的\(g\)里面最小的那个，因为如果不是，那么显然不满足我们最小化的条件，从一个更大的走到了本应该可以更小的。

所以我们每次剩下的点中找到一个最小的\(\frac{g_{j}}{\prod_{g_k<g_j}(1-p_{j,k})}\)来更新它对其他点的影响即可。

时间复杂度\(O(n^2)\)

code

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=1100;

int n;bool v[N];

double p[N][N],prod[N],f[N];

int main()

{

	scanf("%d",&n);

	for(int i=1;i<=n;i++){

		for(int j=1;j<=n;j++){

			scanf("%lf",&p[i][j]);

			p[i][j]/=100.0;

		}

	}

	if(n==1)return puts("0")&0;

	for(int i=1;i<n;i++)

		prod[i]=1-p[i][n],f[i]=1;

	v[n]=1;

	while(1){

		double low=1e9;int x;

		for(int i=1;i<=n;i++)

			if(f[i]/(1-prod[i])<low&&!v[i])

				low=f[i]/(1-prod[i]),x=i;

		if(x==1)return printf("%.10lf",low)&0;

		v[x]=1;

		for(int i=1;i<=n;i++){

			if(v[i])continue;

			f[i]+=low*p[i][x]*prod[i];

			prod[i]*=(1-p[i][x]);

		}

	}

	return 0;

}

巴特西

CF605E-Intergalaxy Trips【期望dp】

正题

题目大意

解题思路

code

最新文章

热门文章