M_sea

UVA1498 Activation
UVaLuoguVjudge洛谷上的翻译不是很清楚,建议直接看英文题面。分析首先把 $p_4=0$ 的情况判掉,答...
扫描右侧二维码阅读全文
03
2019/09

UVA1498 Activation

UVa

Luogu

Vjudge

洛谷上的翻译不是很清楚,建议直接看英文题面。

分析

首先把 $p_4=0$ 的情况判掉,答案显然为 $0$ 。

考虑 DP 。设 $dp_{i,j}$ 表示 $i$ 个人的队列,现在在第 $j$ 个,最后在前 $k$ 个位置的概率。

转移可以考虑后继状态,容易得到

$$ dp_{i,j}=\begin{cases}dp_{i,j}\times p_1+dp_{i,i}\times p_2+p_4,&j=1\\dp_{i,j}\times p_1+dp_{i,j-1}\times p_2+dp_{i-1,j-1}\times p_3+p_4,&2\leq j\leq k\\dp_{i,j}\times p_1+dp_{i,j-1}\times p_2+dp_{i-1,j-1}\times p_3,&k+1\leq j\leq i\end{cases} $$

我们先考虑消掉等号右边的 $dp_{i,j}$ 。将带有 $dp_{i,j}$ 的项移项后两边同除 $1-p_1$ 得到

$$ dp_{i,j}=\begin{cases}dp_{i,i}\times\frac{p_2}{1-p_1}+\frac{p_4}{1-p_4},&j=1\\dp_{i,j-1}\times \frac{p_2}{1-p_1}+dp_{i-1,j-1}\times\frac{p_3}{1-p_1}+\frac{p_4}{1-p_1},&2\leq j\leq k\\dp_{i,j-1}\times\frac{p_2}{1-p_1}+dp_{i-1,j-1}\times\frac{p_3}{1-p_1},&k+1\leq j\leq i\end{cases} $$

然而这个东西还是无法转移,于是我们考虑用一些奇技淫巧算出 $dp_{i,i}$ 来,这样子其它的 DP 值就都可以算出了。

注意到

$$ \begin{aligned} dp_{i,1}&=dp_{i,i}\times\frac{p_2}{1-p_1}+\frac{p_4}{1-p_4}\\ dp_{i,2}&=dp_{i,1}\times\frac{p_2}{1-p_1}+dp_{i-1,1}\times\frac{p_3}{1-p_1}+\frac{p_4}{1-p_4}\\ &\cdots\\ dp_{i,i}&=dp_{i,j-1}\times\frac{p_2}{1-p_1}+dp_{i-1,j-1}\times\frac{p_3}{1-p_1}\left(+\frac{p_4}{1-p_4}\right) \end{aligned} $$

于是我们可以上面的式子代入下面的式子中,最后会得到

$$ dp_{i,i}=a^i\times dp_{i,i}+c $$

这里的 $c$ 是一个可以算出的常数。于是我们可以得到 $dp_{i,i}=\frac{c}{1-a^i}$ 。

最后考虑边界的问题。注意到

$$ dp_{1,1}=dp_{1,1}\times p_1+dp_{1,1}\times p_2+p_4 $$

于是可以得到 $dp_{1,1}=\frac{p_4}{1-p_1-p_2}$ 。

具体实现及细节见代码。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=2000+10;

int n,m,k; double p1,p2,p3,p4;
double pw[N],p[N],dp[N][N];

int main() {
    while (scanf("%d%d%d%lf%lf%lf%lf",&n,&m,&k,&p1,&p2,&p3,&p4)==7) {
        if (p4<1e-6) { puts("0.00000"); continue; }
        for (re int i=pw[0]=1;i<=n;++i) pw[i]=pw[i-1]*p2/(1-p1);
        dp[1][1]=p4/(1-p1-p2);
        for (re int i=2;i<=n;++i) {
            p[1]=p4/(1-p1);
            for (re int j=2;j<=k;++j) p[j]=p3/(1-p1)*dp[i-1][j-1]+p4/(1-p1);
            for (re int j=k+1;j<=i;++j) p[j]=p3/(1-p1)*dp[i-1][j-1];
            double c=0;
            for (re int j=1;j<=i;++j) c+=pw[i-j]*p[j];
            dp[i][i]=c/(1-pw[i]); dp[i][1]=p2/(1-p1)*dp[i][i]+p4/(1-p1);
            for (re int j=2;j<i;++j) dp[i][j]=p2/(1-p1)*dp[i][j-1]+p[j];
        }
        printf("%.5lf\n",dp[n][m]);
    }
    return 0;
}
最后修改:2019 年 09 月 03 日 07 : 55 PM

发表评论