Codeforces 293D Ilya and Escalator：概率 DP 計算期望人數

題目大意

n 人排隊等電梯。每秒：隊首的人以概率 p 進入電梯，概率 1-p 留在原地。t 秒後，電梯裡期望有多少人？

DP 狀態定義

`dp[i][j]` = 第 i 秒結束時，電梯裡有 j 人的概率。
初始：`dp[0][0] = 1`。
轉移：

• 若 `j > 0`：`dp[i][j] = dp[i-1][j-1] * p + dp[i-1][j] * (1-p)` (有人進入 或 無人進入)
• 若 `j == 0`：`dp[i][0] = dp[i-1][0] * (1-p)` (無人進入)
• 邊界：`j` 不超過 `min(i, n)`。當 `j == n` 時，所有人已進入，後續 `dp[i][n] += dp[i-1][n]` (保持滿載)。

期望計算

`E = Σ j * dp[t][j]` (j=1..min(n,t))

代碼實現 (C++)

#include 
#include 
using namespace std;

double dp[2005][2005];

int main() {
    int n, t; double p;
    while (scanf("%d%lf%d", &n, &p, &t) == 3) {
        for (int i = 0; i <= t; i++)
            for (int j = 0; j <= n; j++)
                dp[i][j] = 0;
        dp[0][0] = 1;
        for (int i = 1; i <= t; i++) {
            for (int j = 0; j <= n; j++) {
                if (j > 0) dp[i][j] += dp[i-1][j-1] * p;
                if (j < n) dp[i][j] += dp[i-1][j] * (1 - p);
                else dp[i][j] += dp[i-1][j]; // j==n 已滿
            }
        }
        double ans = 0;
        for (int j = 1; j <= n; j++) ans += j * dp[t][j];
        printf("%.7f\n", ans);
    }
    return 0;
}

優化：滾動數組

只依賴上一行，可用 `dp[2][2005]` 交替，空間優化至 O(n)。

複雜度

• 時間：O(t * n) ≤ 2000 * 2000 = 4e6，極快。
• 空間：O(n) 滾動數組或 O(t*n) 全表。