HDU4089 Activation(困难的循环期望dp)_Python

HDU4089 Activation(困难的循环期望dp)

解题思路摘自kuangbin博客

题意：
有n个人排队等着在官网上激活游戏。Tomato排在第m个。
对于队列中的第一个人。有一下情况：
1、激活失败，留在队列中等待下一次激活（概率为p1)
2、失去连接，出队列，然后排在队列的最后（概率为p2）
3、激活成功，离开队列（概率为p3）
4、服务器瘫痪，服务器停止激活，所有人都无法激活了。
求服务器瘫痪时Tomato在队列中的位置<=k的概率

定义 $d p [i] [j]$ 为总共还 $i$ 个人,自己排在第 $j$ 位到达目标的概率

$j = = 1 ： d p [i] [1] = d p [i] [1] * p 1 + d p [i] [i] * p 2 + p 4$

$1 < j < = k : d p [i] [j] = d p [i] [j] * p 1 + d p [i] [j - 1] * p 2 + d p [i - 1] [j - 1] * p 3 + p 4$

$k < j < = i : d p [i] [j] = d p [i] [j] * p 1 + d p [i] [j - 1] * p 2 + d p [i - 1] [j - 1] * p 3$

上面三个式子化简分别得到

$j = = 1 ： d p [i] [1] = d p [i] [i] * p 21 + p 41$

$1 < j < = k : d p [i] [j] = d p [i] [j - 1] * p 21 + d p [i - 1] [j - 1] * p 31 + p 41$

$k < j < = i : d p [i] [j] = d p [i] [j - 1] * p 21 + d p [i - 1] [j - 1] * p 31$

这样如果递推 $d p [i] [1, n]$ , $d p [i - 1] [1, n]$ 已经是常数了

所以对于特定的 $i$ ,实际上三个式子可以再次化简

$j = = 1 ： d p [i] [1] = d p [i] [i] * p 21 + 某常数$

$1 < j < = k : d p [i] [j] = d p [i] [j - 1] * p 21 + 某常数$

$k < j < = i : d p [i] [j] = d p [i] [j - 1] * p 21 + 某常数$

如此一来就是 $n$ 个方程组解 $n$ 个未知数了

我们可以先从尾到头迭代解得 $d p [i] [i]$ 即可

复杂度就是 $O(n^2)$

#include <bits/stdc++.h>
using namespace std;
const int maxn=2009;
const double eps=1e-7;
int n,m,k;
double dp[maxn][maxn],g[maxn],p1,p2,p3,p4,c[maxn];
int main()
{
	while( cin >> n >> m >> k >> p1 >> p2 >> p3 >> p4 )
	{
		double sumn=0;
		if( p4<eps )
		{
			printf("0.00000\n");
			continue;
		}
		dp[1][1] = p4/(p3+p4);
		double p21=p2/(1-p1), p31=p3/(1-p1), p41 = p4/(1-p1);
		int u=1,v=0;
		for(int i=2;i<=n;i++)
		{
			u^=1, v^=1;
			c[1]=p41;
			for(int j=2;j<=k;j++)	c[j]=p31*dp[v][j-1]+p41;
			for(int j=k+1;j<=i;j++)	c[j]=p31*dp[v][j-1];
			dp[u][i]=0;
			double p=1;
			for(int j=i;j>=1;j--)
			{
				dp[u][i]+=p*c[j];
				p*=p21;
			}
			dp[u][i]/=(1-p);
			dp[u][1]=p21*dp[u][i]+c[1];
			for(int j=2;j<i;j++)
				dp[u][j]=p21*dp[u][j-1]+c[j];
		}
		printf("%.5lf\n",dp[u][m] );
	}
}

本文地址：https://blog.csdn.net/jziwjxjd/article/details/109005016