有生以来见过的最恶心的 DP 题目。

---

题意：n 个人排队激活仙剑奇侠 5. 服务器会按队列顺序进行激活操作。但是在激活队首顾客时，会有以下 4 中情况：

1. 激活失败，重试：概率 p1
2. 链接丢失，队首顾客被扔到队尾：概率 p2
3. 激活成功：队首顾客消失
4. 服务器错误：服务器被关闭，队列里的所有顾客的请求失效。

现在排在第 m 个的人想知道，有多大的可能性他前面有少于 k 个人时服务器关闭，因为这样是很操蛋的 (原文是 suck)

---

思路：很直接想到用 f[i][j] 表示有 i 个人排队站在第 j 个时出现 suck 情况的概率。那么… 然后一阵沉默.

\begin{equation}
f[i][1]=f[i][1]P_1+f[i][i]P_2+P_4
\end{equation}
\begin{equation}
f[i][j]=f[i][j]P_1+f[i][j-1]P_2+f[i-1][j-1]P_3 (j>k)
\end{equation}
\begin{equation}
f[i][j]=f[i][j]P_1+f[i][j-1]P_2+f[i-1][j-1]P_3+P_4 (j<=k)
\end{equation}

移项。

令 $P_{21}=\frac{P_2}{1-P_1}$,$P_{31}=\frac{P_3}{1-P_1}$,$P_{41}=\frac{P_4}{1-P_1}$

设一个数组 C[]

$$
\begin{cases}
C[j]&f[i-1][j-1]P_{31}(j>k) \\
C[j]&f[i-1][j-1]P_{31}+P_{41}(j<=k)
\end{cases}
$$

那么

$$
f[i][1]=f[i][i] P _ {21}+ P _ {41}\\
f[i][j]=f[i][j-1] P _ {21}+C[j]
$$

这样我们就可以递推了

。

吗？

由于 f[i][1] 和 f[i][i] 互相依赖，所以呵呵。

于是我们得手动列出 f[i][j] 的表达式，手动代入消元

然后可以得到：

$$
f[i][i]=\frac{\sum{P _ {21}^{i-x}C[x]} _ {x=1}^{i}}{1-P _ {21}^i}
$$

然后就可以用 f[i][i] 开始递推了

#include <iostream>
#include <cstdio>
#include <cstring>

#define MX 2009

using namespace std;

double f[MX][MX];
double c[MX];
int n,m,tar;
double p1,p2,p3,p4,p21,p31,p41;
double sum,p;

int main()
{
    while(scanf("%d%d%d%lf%lf%lf%lf",&n,&m,&tar,&p1,&p2,&p3,&p4)!=EOF)
    {
        if(p4<=0.000001){printf("0.00000\n");continue;}
        p21=p2/(1-p1),p31=p3/(1-p1),p41=p4/(1-p1);
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=i;j++)c[j]=(j>tar?f[i-1][j-1]*p31:f[i-1][j-1]*p31+p41);
            sum=0,p=1;
            for(int j=0;j<=i-1;j++)sum+=c[i-j]*p,p*=p21;
            f[i][i]=sum/(1-p);
            f[i][1]=f[i][i]*p21+p41;
            for(int j=2;j<=i;j++)f[i][j]=f[i][j-1]*p21+c[j];
        }
        printf("%.5f\n",f[n][m]);
    }
    return 0;
}