要在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)，其他的就可以按照最开始的式子递推了。
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <cmath> 5 using namespace std; 6 7 const int maxn = 2000 + 10; 8 int n, m, k; 9 double p1, p2, p3, p4; 10 double d[2][maxn]; 11 12 const double eps = 1e-8; 13 14 int dcmp(double x) 15 { 16 if(fabs(x) < eps) return 0; 17 return x < 0 ? -1 : 1; 18 } 19 20 int main() 21 { 22 while(scanf("%d%d%d", &n, &m, &k) == 3 && n) 23 { 24 scanf("%lf%lf%lf%lf", &p1, &p2, &p3, &p4); 25 26 if(dcmp(p3 - 1) == 0 || dcmp(p4) == 0) { puts("0.00000"); continue; } 27 28 memset(d, 0, sizeof(d)); 29 d[1][1] = p4 / (1.0 - p1 - p2); 30 double p21 = p2 / (1.0 - p1); 31 double p31 = p3 / (1.0 - p1); 32 double p41 = p4 / (1.0 - p1); 33 34 int cur = 1; 35 36 for(int i = 2; i <= n; i++) 37 { 38 cur = 1 - cur; 39 40 double a = 1.0, b = 0; 41 for(int j = 2; j <= i; j++) 42 { 43 a *= p21; 44 b = b * p21 + d[1-cur][j-1] * p31; 45 if(j <= k) b += p41; 46 } 47 48 d[cur][i] = (a * p41 + b) / (1.0 - a * p21); 49 d[cur][1] = p21 * d[cur][i] + p41; 50 51 for(int j = 2; j < i; j++) 52 { 53 d[cur][j] = p21 * d[cur][j-1] + p31 * d[1-cur][j-1]; 54 if(j <= k) d[cur][j] += p41; 55 } 56 } 57 58 printf("%.5f ", d[cur][m]); 59 } 60 61 return 0; 62 }