有生以来见过的最恶心的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{equation}
\left{
\begin{aligned}
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{aligned}
\right.
\end{equation}

那么

\begin{equation}
f[i][1]=f[i][i]P_{21}+P_{41}
\end{equation}
\begin{equation}
f[i][j]=f[i][j-1]P_{21}+C[j]
\end{equation}

这样我们就可以递推了

吗?

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

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

然后可以得到:

\begin{equation}
f[i][i]=\frac{\sum{P_{21}^{i-x}C[x]}{x=1}^{i}}{1-P{21}^i}
\end{equation}

然后就可以用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;
}

分类: 文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *