题意：激活游戏需要排队，排队时，每次操作可能发生如下情况：1、队首的人激活失败，则队伍顺序不变，等待下次操作，概率为p1；2、队首的人掉线了，则他重新排队成为队尾，其他人顺次向前移，概率p2；3、队首的人激活成功，则他出队，其他人顺次向前移，概率p3；4、机器死机，则所有人都不能再激活，队伍顺序维持原状，概率p4。给定n，m，k，初始时，队列一共有n个人，小明排在第m位，问机器死机且死机时小明在队列中且小明前面的人数量不多于k-1个时的概率。
解法：概率DP。虽然求的不是期望是概率，但和求期望的递推思路是一样的。设d[i][j]表示现在有i个人排队，小明排在第j位，要转移到目标状态的概率。状态转移方程为：
初始时，d[1][1] = p4 / (1 - p1 - p2)；
当j == 1，d[i][1] = d[i][1]*p1 + d[i][i]*p2 + p4；
当j <= k，d[i][j] = d[i][j]*p1 + d[i][j-1]*p2 + d[i-1][j-1]*p3 + p4；
当j > k，d[i][j] = d[i][j]*p1 + d[i][j-1]*p2 + d[i-1][j-1]*p3。
为了方便，记p21 = p2 / (1 - p1)，p31 = p3 / (1 - p3)，p41 = p4 / (1 - p4)。
当j == 1，d[i][1] = d[i][i] * p21 + p41；
当j <= k，d[i][j] = d[i][j-1]*p21 + d[i-1][j-1]*p31 + p41；
当j > k，d[i][j] = d[i][j-1]*p21 + d[i-1][j-1]*p31。
注意到，当j == 1，d[i][j] 由d[i][i](i >= j)推出，而当j > 1，d[i][j]由d[i][j-1]和d[i-1][j-1]推出，这样的话是带环的，不能直接用递推解决，而要用到高斯消元(好像用高斯消元会超时)。而此处，实际上是能够通过迭代解决问题的，即对每个i，递推前先求处d[i][i]。
将d[i][j]写成d[i][j-1]*p21 + c[j]的或者d[i][1]*p21 + c[1]的形式，其中c[j]要分情况讨论。
当j == 1，c[j] = p41；
当j <= k，c[j] = p41 + d[i-1][j-1]*p31；
当j > k，c[j] = d[i-1][j-1]*p31；
其中，由于d[i-1][j-1]已经求出，所以c[j]均为常数。
则易推得，d[i][i] = d[i][i] * p21^i + c[1]*p21^(i-1) + c[2]*p21^(i-2) + ... c[2]*p21 + c[1]。
这样，这道题就得到了解决。不过不要忘记，p4 = 0要特判，否则会错的！
Ps:原来这是一道区域赛原题....2011 Asia Beijing Regional Contest，而且是里面第四简单的- -。看了一下现场赛的排名，1题快点就能铜，过了4题的队只有两个不是金牌- -，当然应该是那年去这个赛区的队都太弱了.....不过想一下，懂了以后也没有觉得这道题太难吧......
tag:math, 概率DP，good
1 /* 2 * Author: Plumrain 3 * Created Time: 2013-10-31 19:59 4 * File Name: DP-HDU-4089.cpp 5 */ 6 #include<iostream> 7 #include<cstdio> 8 #include<cstring> 9 10 using namespace std; 11 12 const double eps = 1e-8; 13 #define CLR(x) memset(x, 0, sizeof(x)) 14 #define zero(x) (((x)>0?(x):-(x))<eps) 15 16 double d[2005][2005], c[2005]; 17 18 int main() 19 { 20 int n, m, k; 21 double p1, p2, p3, p4; 22 double p21, p31, p41; 23 while (scanf ("%d%d%d", &n, &m, &k) != EOF){ 24 scanf ("%lf%lf%lf%lf", &p1, &p2, &p3, &p4); 25 26 if (zero(p4)){ 27 printf ("0.00000 "); 28 continue; 29 } 30 31 p21 = p2 / (1 - p1); 32 p31 = p3 / (1 - p1); 33 p41 = p4 / (1 - p1); 34 35 CLR (d); d[1][1] = p4 / (1 - p1 - p2); 36 for (int i = 1; i <= n; ++ i){ 37 for (int j = 1; j <= i; ++ j){ 38 if (j == 1) c[j] = p41; 39 else if (j <= k) c[j] = d[i-1][j-1] * p31 + p41; 40 else c[j] = d[i-1][j-1] * p31; 41 } 42 43 double sum = 0.0, cnt = 1.0; 44 for (int j = i; j >= 1; -- j){ 45 sum += c[j] * cnt; 46 cnt *= p21; 47 } 48 if (i > 1) d[i][i] = sum / (1 - cnt); 49 50 for (int j = 0; j <= i; ++ j){ 51 if (j == 1) 52 d[i][j] = d[i][i]*p21 + p41; 53 else if (j <= k) 54 d[i][j] = d[i][j-1]*p21 + d[i-1][j-1]*p31 + p41; 55 else 56 d[i][j] = d[i][j-1]*p21 + d[i-1][j-1]*p31; 57 } 58 } 59 60 printf ("%.5f ", d[n][m]); 61 } 62 return 0; 63 }