HDU-6568 Math 概率、期望

guotiaotiao 2020-05-17

题目链接:HDU-6568 Math

题意

Avin要带着机器人在数轴上从 0 走到 L,他走路按照以下规则:对于每个整数位置

  1. 如果Avin还带着机器人,则有 p 的概率弄丢机器人;
  2. 如果Avin在 i 位置弄丢机器人,则在 [i, L) 每个整数位置有 q 的概率发现,当到达终点 L 却没有机器人,则一定能够发现;
  3. 如果Avin发现弄丢机器人,则会往回走直到遇见机器人,否则他会继续前进。

问Avin从 0 走到 L 的路程期望是多少?


思路

\(f(i)\) 表示从 \(i\) 位置带着机器人,走到 \(i+1\) 位置也带着机器人的路程期望。下面用 \(E\) 来表示各个情况的路程期望。

  1. \(i\) 位置没有弄丢机器人,\(E_1 = 1\)
  2. \(i\) 位置弄丢了机器人,并且直到 \(L\) 才发现,概率为 \((1-q)^{L-i}\),回到 \(i\) 位置的路程为 \(2(L-i)\),所以期望 \(E_2=2(L-i)(1-q)^{L-i}\)
  3. \(i\) 位置弄丢了机器人,但在 \([i, L-1]\) 就发现,则在 \(i+x\) 位置发现的概率为 \(q(1-q)^x\),回到 \(i\) 位置的路程为 \(2x\),枚举 \(x\),则这部分的期望 \(E_3=\sum_{x=0}^{L-i-1}2xq(1-q)^x\)

那么 \(f(i)=(1-p)E_1+p(E_2+E_3)\) ?可以发现 \(E_1\) 算的是走到 \(i+1\) 的路程期望,而 \(E_2、E_3\) 算的是回到 \(i\) 位置的路程期望,所以应该再加上从 \(i\) 走到 \(i+1\) 的路程期望,即 \(f(i) = (1-p)E_1 + p(E_2+E_3+f(i))\) ,移项得 \(f(i)=E_1+\frac{p}{1-p}(E_2+E_3)\) ,对 \(E_3\) 预处理即可 \(O(1)\) 计算 \(f(i)\),最终答案为 \(\sum_{i=0}^{L-1}f(i)\)


代码实现

很坑的一点是,题目没说要处理多组输入,但实际上没写多组输入会WA。

#include <cstdio>
double E3[100010], pow1_q[100010];

int main() {
    int L;
    double p, q;
    while (~scanf("%d %lf %lf", &L, &p, &q)) {
        pow1_q[0] = 1;
        E3[0] = 0;
        for (int x = 1; x <= L; x++) {
            pow1_q[x] = pow1_q[x-1] * (1 - q);
            E3[x] = E3[x-1] + 2 * x * q * pow1_q[x];
        }
        double ans = 0, E2;
        for (int i = 0; i < L; i++) {
            E2 = 2 * (L - i) * pow1_q[L-i];
            ans += 1 + p / (1 - p) * (E2 + E3[L-i-1]);
        }
        printf("%.7f\n", ans);
    }
    return 0;
}

相关推荐