LightOJ - 1408

题意:

一个人在击球,有p的概率集中,有(1-p)的概率击不中。如果能够连续击中x次将停止,连续不集中y次也将停止。问最终停止击球时击球次数的期望。

思路:

设f[i]代表连续击中i次之后距离结束还剩的期望步数。g[i]代表连续不集中i次后距离结束的期望步数。可以列出下列方程:
{f[i]=pf[i+1]+(1p)g[1]+1g[i]=(1p)g[i+1]+pf[1]+1\left\{\begin{aligned} f[i]=p*f[i+1]+(1-p)*g[1]+1\\ g[i]=(1-p)*g[i+1]+p*f[1]+1 \end{aligned}\right.{f[i]=p∗f[i+1]+(1−p)∗g[1]+1g[i]=(1−p)∗g[i+1]+p∗f[1]+1​
边界条件:
{f[x]=0g[y]=0\left\{\begin{aligned} f[x]=0\\ g[y]=0 \end{aligned}\right.{f[x]=0g[y]=0​
答案:
ans=pf[1]+(1p)g[1]ans = p*f[1]+(1-p)*g[1]ans=p∗f[1]+(1−p)∗g[1]

推导过程:

令:
{A=(1p)g[1]+1B=pf[1]+1\left\{\begin{aligned} A &= (1-p)*g[1]+1\\ B&=p*f[1]+1 \end{aligned}\right.{AB​=(1−p)∗g[1]+1=p∗f[1]+1​

则原式:
{f[i]=pf[i+1]+Ag[i]=(1p)g[i+1]+B\left\{\begin{aligned} f[i] &= p*f[i+1]+A\\ g[i]&=(1-p)*g[i+1]+B \end{aligned}\right.{f[i]g[i]​=p∗f[i+1]+A=(1−p)∗g[i+1]+B​
求解f[1]和g[1]:
f[1]=pf[2]+A=p(pf[3]+A)+A=p2f[3]+A(1+p)=px1f[x]+A(1+p+p2+...+px2)=0+A1px11p=A1px11p=(1px1)g[1]+1px11p. \begin{aligned} f[1] &= p*f[2]+A\\ &= p*(p*f[3]+A)+A\\ &= p^2*f[3]+A*(1+p)\\ &=p^{x-1}*f[x]+A*(1+p+p^2+...+p^{x-2})\\ &=0+A*\frac{1-p^{x-1}}{1-p}\\ &=A*\frac{1-p^{x-1}}{1-p}\\ &=(1-p^{x-1})*g[1]+\frac{1-p^{x-1}}{1-p} \end{aligned}. f[1]​=p∗f[2]+A=p∗(p∗f[3]+A)+A=p2∗f[3]+A∗(1+p)=px−1∗f[x]+A∗(1+p+p2+...+px−2)=0+A∗1−p1−px−1​=A∗1−p1−px−1​=(1−px−1)∗g[1]+1−p1−px−1​​.
同理 g[1]=[1(1p)y1]f[1]+1(1p)y1pg[1]=[1-(1-p)^{y-1}]*f[1]+\frac{1-(1-p)^{y-1}}{p}g[1]=[1−(1−p)y−1]∗f[1]+p1−(1−p)y−1​

{C=[1(1p)y1]D=1(1p)y1pE=(1px1)F=1px11p\left\{\begin{aligned} C&= [1-(1-p)^{y-1}]\\ D&=\frac{1-(1-p)^{y-1}}{p}\\ E&=(1-p^{x-1})\\ F&=\frac{1-p^{x-1}}{1-p} \end{aligned}\right.⎩⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎧​CDEF​=[1−(1−p)y−1]=p1−(1−p)y−1​=(1−px−1)=1−p1−px−1​​

{g[1]=Cf[1]+Df[1]=Eg[1]+F\left\{\begin{aligned} g[1]&=C*f[1]+D\\ f[1]&=E*g[1]+F \end{aligned}\right.{g[1]f[1]​=C∗f[1]+D=E∗g[1]+F​
求得f[1]=DE+F1CEf[1]=\frac{DE+F}{1-CE}f[1]=1−CEDE+F​
g[1]=Cf[1]+Dg[1]=C*f[1]+Dg[1]=C∗f[1]+D
带入ans即可。
需要注意p=0或p=1时的情况。
代码

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ld long double
#define ull unsigned long long
#define __ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

const int maxn = 5e5 + 10;
const int maxm = 5e5 + 10;
const ll mod = 1e9 + 7;
const double eps = 1e-10;

ld p, x, y;

int main() {
    __;
    int _;
    cin >> _;
    for (int sce = 1; sce <= _; ++sce) {
        cin >> p >> x >> y;
        cout << "Case " << sce << ": ";
        p = 1.0 - p;
        if (p == 1.0) {
            cout << x << endl;
            continue;
        }
        if (p == 0.0) {
            cout << y << endl;
            continue;
        }
        ld ans = 0;
        ld C = 1.0 - powl(1.0 - p, y - 1.0);
        ld D = (1.0 - powl(1.0 - p, y - 1.0)) / p;
        ld E = (1.0 - powl(p, x - 1.0));
        ld F = (1.0 - powl(p, x - 1.0)) / (1.0 - p);
        ld f1 = (D * E + F) / (1.0 - C * E);
        ld g1 = C * f1 + D;
        cout << fixed << setprecision(10) << (ld) (p * f1 + (1.0 - p) * g1 + 1.0) << endl;
    }
    return 0;
}
上一篇:【转】 前端笔记之JavaScript面向对象(一)Object&函数上下文&构造函数&原型链


下一篇:hive 初始化数据库报错