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

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

解题思路摘自kuangbin博客

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

---

定义

d

p

[

i

]

[

j

]

dp[i][j]

dp[i][j]为总共还

i

i

i个人,自己排在第

j

j

j位到达目标的概率

j

=

=

1

：

d

p

[

i

]

[

1

]

=

d

p

[

i

]

[

1

]

∗

p

1

+

d

p

[

i

]

[

i

]

∗

p

2

+

p

4

j==1：dp[i][1]=dp[i][1]*p1+dp[i][i]*p2+p4

j==1：dp[i][1]=dp[i][1]∗p1+dp[i][i]∗p2+p4

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

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

1<j<=k:dp[i][j]=dp[i][j]∗p1+dp[i][j−1]∗p2+dp[i−1][j−1]∗p3+p4

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

k<j<=i:dp[i][j]=dp[i][j]*p1+dp[i][j-1]*p2+dp[i-1][j-1]*p3

k<j<=i:dp[i][j]=dp[i][j]∗p1+dp[i][j−1]∗p2+dp[i−1][j−1]∗p3

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

j

=

=

1

：

d

p

[

i

]

[

1

]

=

d

p

[

i

]

[

i

]

∗

p

21

+

p

41

j==1：dp[i][1]=dp[i][i]*p21+p41

j==1：dp[i][1]=dp[i][i]∗p21+p41

1

<

j

<

=

k

:

d

p

[

i

]

[

j

]

=

d

p

[

i

]

[

j

−

1

]

∗

p

21

+

d

p

[

i

−

1

]

[

j

−

1

]

∗

p

31

+

p

41

1<j<=k:dp[i][j]=dp[i][j-1]*p21+dp[i-1][j-1]*p31+p41

1<j<=k:dp[i][j]=dp[i][j−1]∗p21+dp[i−1][j−1]∗p31+p41

k

<

j

<

=

i

:

d

p

[

i

]

[

j

]

=

d

p

[

i

]

[

j

−

1

]

∗

p

21

+

d

p

[

i

−

1

]

[

j

−

1

]

∗

p

31

k<j<=i:dp[i][j]=dp[i][j-1]*p21+dp[i-1][j-1]*p31

k<j<=i:dp[i][j]=dp[i][j−1]∗p21+dp[i−1][j−1]∗p31

这样如果递推

d

p

[

i

]

[

1

,

n

]

dp[i][1,n]

dp[i][1,n],

d

p

[

i

−

1

]

[

1

,

n

]

dp[i-1][1,n]

dp[i−1][1,n]已经是常数了

所以对于特定的

i

i

i,实际上三个式子可以再次化简

j

=

=

1

：

d

p

[

i

]

[

1

]

=

d

p

[

i

]

[

i

]

∗

p

21

+

某

常

数

j==1：dp[i][1]=dp[i][i]*p21+某常数

j==1：dp[i][1]=dp[i][i]∗p21+某常数

1

<

j

<

=

k

:

d

p

[

i

]

[

j

]

=

d

p

[

i

]

[

j

−

1

]

∗

p

21

+

某

常

数

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

1<j<=k:dp[i][j]=dp[i][j−1]∗p21+某常数

k

<

j

<

=

i

:

d

p

[

i

]

[

j

]

=

d

p

[

i

]

[

j

−

1

]

∗

p

21

+

某

常

数

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

k<j<=i:dp[i][j]=dp[i][j−1]∗p21+某常数

如此一来就是

n

n

n个方程组解

n

n

n个未知数了

我们可以先从尾到头迭代解得

d

p

[

i

]

[

i

]

dp[i][i]

dp[i][i]即可

复杂度就是

O

(

n

2

)

O(n^2)

O(n2)

#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