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

传送门啊啊啊啊啊啊啊啊啊啊啊

解题思路摘自kuangbin博客

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

---

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

$$j==1：dp[i][1]=dp[i][1]\ast p1+dp[i][i]\ast p2+p4$$

$$1<j<=k:dp[i][j]=dp[i][j]\ast p1+dp[i][j-1]\ast p2+dp[i-1][j-1]\ast p3+p4$$

$$k<j<=i:dp[i][j]=dp[i][j]\ast p1+dp[i][j-1]\ast p2+dp[i-1][j-1]\ast p3$$

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

$j==1：dp[i][1]=dp[i][i]\ast p21+p41$

$$1<j<=k:dp[i][j]=dp[i][j-1]\ast p21+dp[i-1][j-1]\ast p31+p41$$

$k<j<=i:dp[i][j]=dp[i][j-1]\ast p21+dp[i-1][j-1]\ast p31$

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

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

$j==1：dp[i][1]=dp[i][i]\ast p21+某常数$

$1<j<=k:dp[i][j]=dp[i][j-1]\ast p21+某常数$

$k<j<=i:dp[i][j]=dp[i][j-1]\ast p21+某常数$

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

我们可以先从尾到头迭代解得$dp[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