题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4089
题意：
有n个人在排队激活游戏，Tomato排在第m个。
每次队列中的第一个人去激活游戏，有可能发生以下四种情况：
（1）激活失败，继续留在队首，等待下一次激活。
（2）连接失败，退到队尾。
（3）激活成功，离开队列。
（4）服务器瘫痪。
发生的概率分别为p1,p2,p3,p4。
问你服务器瘫痪时，Tomato的位置<=k的概率。
题解：
表示状态：
dp[i][j] = probability
表示当前还有i个人在排队，Tomato在位置j。在这以及之后服务器瘫痪时，Tomato位置<=k的概率。
找出答案：
ans = dp[n][m]
如何转移:
按着四种情况分别写就好：
（1）j == 1: dp[i][1] = dp[i][1]*p1 + dp[i][i]*p2 + p4
（2）2<=j<=k: dp[i][j] = dp[i][j]*p1 + dp[i][j-1]*p2 + dp[i-1][j-1]*p3 + p4
（3）k<j<=i: dp[i][j] = dp[i][j]*p1 + dp[i][j-1]*p2 + dp[i-1][j-1]*p3
令p21 = p2/(1-p1), p31 = p3/(1-p1), p41 = p4/(1-p1)
化简得：
（1）j == 1: dp[i][1] = dp[i][i]*p21 + p41
（2）2<=j<=k: dp[i][j] = dp[i][j-1]*p21 + dp[i-1][j-1]*p31 + p41
（3）k<j<=i: dp[i][j] = dp[i][j-1]*p21 + dp[i-1][j-1]*p31
边界条件：
dp[1][1] = dp[1][1]*(p1+p2) + p4
解得：dp[1][1] = p4/(1-p1-p2)
然而这并没有结束……
转移的时候显然先枚举i，在枚举j。
可是j在当前的i中，是往两个方向转移的：
dp[i][j]需要用到前面的dp[i][j-1]，而dp[i][1]又用到了后面的dp[i][i]……QAQ
所以迭代一下，先解出dp[i][1]：
每一个dp[i][j]都可以表示成 dp[i][j] = p*dp[i][1] + c 的形式。
显然对于最初的dp[i][1]: p = 1, c = 0
对于后面的每一个dp[i][j]: p *= p21, c = c*p21 + dp[i-1][j-1]*p31 + (j<=k)*p41
这样就由前一项的p和c，推出了当前的p和c。
推啊推，直到推出了：dp[i][i] = p*dp[i][1] + c
这时就可以代入解方程了：
代入原来的递推式dp[i][1] = dp[i][i]*p21 + p41中
得到：dp[i][1] = p21*(p*dp[i][1] + c) + p41
解得：dp[i][1] = (p21*c + p41)/(1 - p*p21)
然而还是没有结束……
这题丧病卡空间……所以用滚动数组。
由于转移的时候要用到dp[0][j]的0值，所以第一维MAX_N变成3，i=1,2轮流使用。
这样就好啦~~~
AC Code:
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 2005
#define cal(x) ((!(x))?0:(2-((x)&1))) using namespace std; int n,m,k;
double p1,p2,p3,p4;
double dp[][MAX_N]; int main()
{
memset(dp,,sizeof(dp));
while(scanf("%d%d%d%lf%lf%lf%lf",&n,&m,&k,&p1,&p2,&p3,&p4)!=EOF)
{
if(p4<1e-)
{
printf("0.00000\n");
continue;
}
double p21=p2/(-p1);
double p31=p3/(-p1);
double p41=p4/(-p1);
dp[cal()][]=p4/(-p1-p2);
for(int i=;i<=n;i++)
{
if(i>)
{
double p=1.0,c=;
for(int j=;j<=i;j++)
{
p*=p21;
c=c*p21+dp[cal(i-)][j-]*p31;
if(j<=k) c+=p41;
}
dp[cal(i)][]=(c*p21+p41)/(-p*p21);
}
for(int j=;j<=i;j++)
{
dp[cal(i)][j]=dp[cal(i)][j-]*p21+dp[cal(i-)][j-]*p31;
if(j<=k) dp[cal(i)][j]+=p41;
}
}
printf("%.5f\n",dp[cal(n)][m]);
}
}