Hellc

【题目描述】

有 $N$ 个人排成一队，每秒，队首的人有 $p$ 的概率走上电梯（此后就一直待在上面），或有 $1 - p$ 的概率不动，求 $T$ 秒过后，电梯上的人数的期望。

【题目链接】

CF 518D Ilya and Escalator

【解题思路】

我们直接考虑期望的定义：随机变量 $x$ 的期望 $E[x]$ 是 $x$ 所有取值按概率加权的和。

在本题中，如果设 $f[i][j]$ 表示 $i$ 秒后电梯上有 $j$ 个人的概率，那么答案即为： $$ ans = \sum_{1 \leq j \leq N} f[T][j] \times j $$

如何求 $f[i][j]$ 呢？

当 $j \lt N$ 时，考虑第一个人上或不上电梯，容易得到：

$$ f[i + 1][j + 1] \leftarrow f[i][j] \times p $$

$$ f[i + 1][j] \leftarrow f[i][j] \times (1 - p) $$

当 $j = N$ 时，所有的人都在电梯上了，下一秒必然也是如此： $$ f[i + 1][N] \leftarrow f[i][N] $$

总结：考虑期望的定义，将其转化成求概率的问题。

【AC代码】

第一次在 CF 上做题。

#include <iostream>
#include <iomanip>

const int MAXT = 2000;
const int MAXN = 2000;

int n, t;
double p;

double f[MAXT + 1][MAXN + 1];

inline double solve(){
    f[0][0] = 1;
    for(int i = 0; i < t; i++){
        for(int j = 0; j < n; j++){
            f[i + 1][j + 1] += f[i][j] * p;
            f[i + 1][j] += f[i][j] * (1 - p);
        }

        f[i + 1][n] += f[i][n];
    }

    double ans = 0;
    for(int i = 0; i <= n; i++) ans += i * f[t][i];

    return ans;
}

int main(){
    std::cin >> n >> p >> t;

    std::cout.setf(std::ios::fixed);
    std::cout << std::setprecision(6) << solve() << std::endl;

    return 0;
}

就是这样啦~