HDU 4089 Activation(11年北京概率问题)

来源：岁月联盟编辑：exp 时间：2012-08-30

题目：仙5的激活序列。有以下4种情况：

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

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

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

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

求主角的位置在K以内，而且服务器崩溃的概率

http://acm.hdu.edu.cn/showproblem.php?pid=4089

比较容易想到一个二维DP

dp[i][j]表示队列总共有i个人，主角站在第j个位置时，所求事件发生的概率。

那么可以写出转移方程

dp[i][1]=dp[i][1]*p1+dp[i][i]*p2+p4 (可能自己注册失败，第二次继续，可能自己连接失败，回到队尾，服务器崩溃)

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

dp[i][j]=dp[i][j]*p1+dp[i][j-1]*p2+dp[i-1][j-1]*p3 (j>k)

稍微整理下，把dp[i][j]放到一边

而且令 p21=p2/(1-p2) p31=p3/(1-p1) p41=p4/(1-p1);

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

dp[i][j]=dp[i][j-1]*p21+dp[i-1][j-1]*p31+p41; (j<=k)

dp[i][j]=dp[i][j-1]*p21+dp[i-1][j-1]*p31; (j>k)

可以发现后面的部分dp[i-1][j-1]在递推的时候都可以解决，我们令后面的部分为c[j]

则c[1]=p41 c[2]=dp[i-1][j-1]*p31+p41 …………

dp[i][j]就可以由dp[i][j-1]推出，但是可以发现这里产生了一个循环，dp[i][1]又是由dp[i][i]得来的。

范围如此之大，肯定不能用高斯消元来做，而且也没必要。

我们把式子合并，迭代一下，这样就能先解出dp[i][i],进而可以得到dp[i][1],剩下的就可以递推出来了

dp[i][i]=dp[i][i]*p21^i+c[2]^p21^(i-1)……c[i]+p41*p21

题目要求的便是Dp[n][m];

[cpp]
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define eps 1e-10
#define N (1<<7)+5
#define inf 1<<20
#define zero(a) (fabs(a)<eps)
#define lson (step<<1)
#define rson (step<<1|1)
using namespace std;
double p1,p2,p3,p4,p21,p31,p41;
double dp[2005][2005],c[2005];
int n,m,k;
int main(){
    while(scanf("%d%d%d%lf%lf%lf%lf",&n,&m,&k,&p1,&p2,&p3,&p4)!=EOF){
        if(zero(p4)) {puts("0.00000");continue;}
        p21=p2/(1-p1);
        p31=p3/(1-p1);
        p41=p4/(1-p1);
        dp[1][1]=p4/(1-p1-p2);
        for(int i=2;i<=n;i++){
            for(int j=2;j<=(i<k?i:k);j++)
               c[j]=dp[i-1][j-1]*p31+p41;
            for(int j=k+1;j<=i;j++)
               c[j]=dp[i-1][j-1]*p31;
            double p=1,tmp=0;
            for(int j=i;j>1;j--){
                tmp+=p*c[j];
                p*=p21;
            }
            dp[i][i]=(tmp+p*p41)/(1-p*p21);
            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;
}

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define eps 1e-10
#define N (1<<7)+5
#define inf 1<<20
#define zero(a) (fabs(a)<eps)
#define lson (step<<1)
#define rson (step<<1|1)
using namespace std;
double p1,p2,p3,p4,p21,p31,p41;
double dp[2005][2005],c[2005];
int n,m,k;
int main(){
    while(scanf("%d%d%d%lf%lf%lf%lf",&n,&m,&k,&p1,&p2,&p3,&p4)!=EOF){
        if(zero(p4)) {puts("0.00000");continue;}
        p21=p2/(1-p1);
        p31=p3/(1-p1);
        p41=p4/(1-p1);
        dp[1][1]=p4/(1-p1-p2);
        for(int i=2;i<=n;i++){
            for(int j=2;j<=(i<k?i:k);j++)
               c[j]=dp[i-1][j-1]*p31+p41;
            for(int j=k+1;j<=i;j++)
               c[j]=dp[i-1][j-1]*p31;
            double p=1,tmp=0;
            for(int j=i;j>1;j--){
                tmp+=p*c[j];
                p*=p21;
            }
            dp[i][i]=(tmp+p*p41)/(1-p*p21);
            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;
}