题目的意思是,Tomato在排队激活游戏,有四种情况:

1、注册失败,但是不影响队列顺序 ,概率为p1

2、连接失败,队首的人排到队尾,概率为p2

3、注册成功,队首离开队列,概率为p3

4、服务器崩溃,激活停止,概率为p4

现在给出总排队人数n,Tomato排在第m个,一个数k,然后是四种情况的概率p1-p4;

如果Tomato前面在k-1个人之内,并且服务器崩溃了,那么这种情况Tomato认为服务器是很low的。问你,发生这种很low的情况的概率。

设dp[i][j]为目前有i个人排队,Tomato排在第j个位置发生这种情况的概率。

当j=1时,dp[i][j] = p1*dp[i][j]+p2*dp[i][i]+p4;

当1<j<=k时,dp[i][j]= p1*dp[i][j]+p2*dp[i][j-1]+p3*dp[i-1][j-1]+p4;

当k<j<=i时,dp[i][j] = p1*dp[i][j]+p2*dp[i][j-1]+p3*dp[i-1][j-1];


化简可得:

当j=1时,dp[i][j] = p21*dp[i][i]+p41;

当1<j<=k时,dp[i][j]= p21*dp[i][j-1]+p31*dp[i-1][j-1]+p41;

当k<j<=i时,dp[i][j] = p21*dp[i][j-1]+p31*dp[i-1][j-1];

其中:p21=p2/(1-p1)、p31=p3/(1-p1)、p41=p4/(1-p1);


循环i:1-n;

由上面的式子可以看出,求dp[i][j]的时候dp[i-1][j-1]是已经计算出来了的。我们不妨把后面的部分用c数组保存起来,得到:

当j=1时,dp[i][j] = p21*dp[i][i]+c[1];

当1<j<=k时,dp[i][j]= p21*dp[i][j-1]+c[j],其中,c[j]=p31*dp[i-1][j-1]+p41;

当k<j<=i时,dp[i][j] = p21*dp[i][j-1]+c[j],其中c[j]=p31*dp[i-1][j-1];


显然,dp[i][1]与dp[i][i]有关,而dp[i][j]又与dp[i][j-1]有关,这样就形成了一个环。所以,我们先利用上面3个式子迭代求出dp[i][i]:

dp[i][i]=dp[i][i]*p21^i+c[1]*p21^i-1+c[2]*p21^i-2+......+c[i];变个形即可求出dp[i][i]

得出dp[i][i],那么dp[i][1]也可以得出,之后就递推就行了。


注意一点,当p4小于1e-5的时候根本不会崩溃了。

StatusAccepted
Time717ms
Memory24416kB
Length1054
LangC++
#include <iostream>
#include <cstdio>
#include <memory.h>
using namespace std;
const int maxn = 2005;
int n, m, k;
double p1, p2, p3, p4, p21, p31, p41;
double dp[maxn][maxn], c[maxn];
double eps = 1e-5;
int main()
{
    while(~scanf("%d%d%d%lf%lf%lf%lf", &n, &m, &k, &p1, &p2, &p3, &p4)){
        if(p4<eps){
            printf("0.00000\n");continue;
        }
        p21 = p2/(1-p1);
        p31 = p3/(1-p1);
        p41 = p4/(1-p1);
        dp[1][1]=p41/(1-p21);
        for(int i=2;i<=n;i++){
            for(int j=1;j<=i;j++){
                if(j==1)c[j]=p41;
                else if(j<=k)c[j]=p31*dp[i-1][j-1]+p41;
                else c[j]=p31*dp[i-1][j-1];
            }
            double tmp=0, pp=1;
            for(int j=i;j>=1;j--){
                tmp+=c[j]*pp;
                pp*=p21;
            }
            dp[i][i]=tmp/(1-pp);
            dp[i][1]=p21*dp[i][i]+p41;
            for(int j=2;j<i;j++){
                dp[i][j]=p21*dp[i][j-1]+c[j];
            }
        }
        printf("%.5f\n", dp[n][m]);
    }
    return 0;
}