HDU4089:Activation(概率DP)

传送门

题意

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

分析

概率DP；
设dp[i][j]表示i个人排队,Tomato排在第j个位置，达到目标状态的概率(j<=i)
dp[n][m]就是所求
(j==1: dp[i][1]=p1*dp[i][1]+p2*dp[i][i]+p4;)
(2<=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][1]=p*dp[i][i]+p41;)
(2<=j<=k: dp[i][j]=p*dp[i][j-1]+p31*dp[i-1][j-1]+p41;)
(k<j<=i: dp[i][j]=p*dp[i][j-1]+p31*dp[i-1][j-1];)

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

在求解dp[i][1~i]时等到下列i个方程
(j==1: dp[i][1]=p*dp[i][i]+c[1];)
(2<=j<=k:dp[i][j]=p*dp[i][j-1]+c[j];)
(k<j=i: dp[i][j]=p*dp[i][j]+c[j];)
其中c[j]都是常数了。上述方程可以解出dp[i][i]了。
首先是迭代得到 dp[i][i].然后再代入就可以得到所有的dp[i][j]了。

注意特判一种情况。就是p4<1e-5的时候，就不会崩溃了，应该直接输出0

以上来自kuangbin的blog，感谢bin神
我补充一些东西
kuangbin的代码在HDOJ上会MLE，我们可以有以下两种选择：
1.改成滚动数组，具体百度
2.double改成float，但是带来另一个问题，精度可能不够，我们把p,p31,p41改成double就行了（比较玄学）
接下来具体说说迭代的过程
dp[i][1]=dp[i][i]p+c[1]
dp[i][[2]=dp[i][1]p+c[2]
...
dp[i][i]=dp[i][i-1]*p+c[i]
将前一个式子乘上p加到后一个式子，最后我们得到这样一个式子：

[dp[i][i]=frac{sum_{k=1}^ic[k]*p^{i-k}}{1-p^i} ]

c[i]=dp[i-1][j-1]*p31+(i<=k)?p41:0;
c[1]=p41;

trick

代码

#include<bits/stdc++.h>
using namespace std;

#define F(i,a,b) for(int i=a;i<=b;++i)
#define mem(a,b) memset(a,b,sizeof(a))

float dp[2020][2020];
int n,m,k;
float c[2020],pp[2020];
float p1,p2,p3,p4;
const double eps=1e-5;
int main()
{
    while(scanf("%d%d%d%f%f%f%f",&n,&m,&k,&p1,&p2,&p3,&p4)!=EOF)
    {
        if(p4<eps) {puts("0.00000");continue;}
        double p=p2/(1-p1);
        double p31=p3/(1-p1);
        double p41=p4/(1-p1);
        pp[0]=1.0;F(i,1,n) pp[i]=p*pp[i-1];
        c[1]=p41;
        dp[1][1]=p41/(1-p);
        for(int i=2;i<=n;++i)
        {
            F(j,2,k) c[j]=p31*dp[i-1][j-1]+p41;
            F(j,k+1,i) c[j]=p31*dp[i-1][j-1];
            double tmp=c[1]*pp[i-1];
            F(j,2,i) tmp+=c[j]*pp[i-j];
            dp[i][i]=tmp/(1-pp[i]);
            dp[i][1]=dp[i][i]*p+c[1];
            F(j,2,i-1) dp[i][j]=dp[i][j-1]*p+c[j];
        }
        printf("%.5f
",dp[n][m]);
    }
    return 0;
}