要在HDU上交的话，要用滚动数组优化一下空间。
这道题想了很久，也算是想明白了，就好好写一下吧。
P1：激活游戏失败，再次尝试。
P2：连接失服务器败，从队首排到队尾。
P3：激活游戏成功，队首的人出队。
P4：服务器down掉，所有人都不能激活了。
设d(i, j)表示i个人排队，主人公排在第j位，发生所求事件的概率。
d(i, 1) = P1 d(i, 1) + P2 d(i, i) + P4 //分别对应激活失败，重新尝试；连接失败排到队尾；服务器down掉
特殊地可以直接计算出 d(1, 1) = (P1 + P2) d(1, 1) + P4
得到：
① j ≤ k，
② j > k，
令
整理上面两个式子得到：
因为是在递推，所以在计算d(i, j)的时候，d(i-1, j-1)的值已经计算出来了。
从d(i, i)开始一直迭代到d(i, 1) (共迭代i-1次)，可以计算出一个d(i, i)和d(i, 1)的关系式，不妨设计算出来的为：d(i, i) = a × d(i, 1) + b
然后再把d(i, i)与d(i, 1)的关系代入：
事实上这里系数a可以直接计算出为：
这样就能计算出d(i, 1)和d(i, i)，其他的就可以按照最开始的式子递推了。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std; const int maxn = + ;
int n, m, k;
double p1, p2, p3, p4;
double d[][maxn]; const double eps = 1e-; int dcmp(double x)
{
if(fabs(x) < eps) return ;
return x < ? - : ;
} int main()
{
while(scanf("%d%d%d", &n, &m, &k) == && n)
{
scanf("%lf%lf%lf%lf", &p1, &p2, &p3, &p4); if(dcmp(p3 - ) == || dcmp(p4) == ) { puts("0.00000"); continue; } memset(d, , sizeof(d));
d[][] = p4 / (1.0 - p1 - p2);
double p21 = p2 / (1.0 - p1);
double p31 = p3 / (1.0 - p1);
double p41 = p4 / (1.0 - p1); int cur = ; for(int i = ; i <= n; i++)
{
cur = - cur; double a = 1.0, b = ;
for(int j = ; j <= i; j++)
{
a *= p21;
b = b * p21 + d[-cur][j-] * p31;
if(j <= k) b += p41;
} d[cur][i] = (a * p41 + b) / (1.0 - a * p21);
d[cur][] = p21 * d[cur][i] + p41; for(int j = ; j < i; j++)
{
d[cur][j] = p21 * d[cur][j-] + p31 * d[-cur][j-];
if(j <= k) d[cur][j] += p41;
}
} printf("%.5f\n", d[cur][m]);
} return ;
}
代码君