题解：P10616 [ICPC2013 WF] Hey, Better Bettor

· · 题解

高考结束了，来复健 OI。

首先考虑赌博的策略。容易发现我们的策略就是当我们赚到 or 亏到一定钱数时，选择继续拼还是及时止损。

因此，设及时收手的边界为 r、及时止损的边界为 -l，以 P 表示最后走到 r 的概率，那么所求的期望就等于 Pr-(1-x)(1-P)l。

我们需要分析 P 和 l,r 之间的关系。不妨把下标都加上 l，记 p_i\;(0\leq i\leq l+r) 表示当前正位于 i，最终走到 l+r 的概率，那么有 p_0=0,p_{l+r}=1，所求的 P=p_l。

接下来建立递推关系。若当前位于位置 k，则有 p 的概率走到 k+1、有 1-p 的概率走到 k-1。于是可以写出 p_k=pp_{k+1}+(1-p)p_{k-1}。

对以上这个方程组，我们发现在边界上有 p_{1}=pp_2，如果反复将其代入后续的式子，可以消成一个单纯的比例关系式。这意味着我们可以用数学方法求出其通解。具体的，若已求出 p_k=f(k)p_{k+1}，就可以代入 p_{k+1}=pp_{k+2}+(1-p)p_k 而解出 p_{k+1}=\dfrac{p}{1-(1-p)f(k)}p_{k+2}。

于是有 f(k+1)=\dfrac{p}{1-(1-p)f(k)}，且 f(1)=p。利用高中数学知识，可以解出 f(n)=\dfrac{p((1-p)^n-p^n)}{(1-p)^{n+1}-p^{n+1}}，从而 p_l=f(l)f(l+1)\cdots f(l+r-1)p_{l+r}=\dfrac{(1-p)^l-p^l}{(1-p)^{l+r}-p^{l+r}}p^r。

记 u=\dfrac{p}{1-p}，有上面的 P=p_l=\dfrac{u^r-u^{l+r}}{1-u^{l+r}}。从而最终的期望 Pr-(1-x)(1-P)l=\dfrac{u^r-u^{l+r}}{1-u^{l+r}}r-(1-x)\dfrac{1-u^r}{1-u^{l+r}}l。

现在，我们的目标就是通过调整 l,r 确定上式的最大值。我们可以感性理解：如果 l 过小，那么不够大胆，收益不大；如果 l 过大，那么止损不及时，收益也不大：也就是说这个函数应当关于 l 是单峰的。同理也应当关于 r 单峰。那么就可以通过三分逐步找到所求的最大期望。

一些可能的细节：

  2. 由于题中的 x,p 均最多有小数点后 2 位，最极限的情况就是 99.99\;49.99。据此，可以预先找到 l,r 的上界。实测 2.5\times10^4 即可。

代码：

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
double x,p,u,pw[50005];
double v(int l,int r)
{
    double n1=pw[r],n2=pw[l+r];
    return (n1-n2)/(1-n2)*r-(1-x)*(1-n1)/(1-n2)*l;
}
double cal(int rr)
{
    double ans=0;int l=1,r=25000;
    while(r-l>=4)
    {
        int m1=l+(r-l)/3,m2=r-(r-l)/3;
        double r1=v(m1,rr),r2=v(m2,rr);
        if(r1>r2) r=m2;
        else l=m1;
    }
    for(int i=l;i<=r;i++) ans=max(ans,v(i,rr));
    return ans;
}
int main()
{
    scanf("%lf%lf",&x,&p);
    x/=100;p/=100;u=p/(1-p);
    pw[0]=1;for(int i=1;i<=50000;i++) pw[i]=pw[i-1]*u;
    double ans=0;
    for(int i=1;i<=25000;i++) ans=max(ans,cal(i));
    printf("%.12lf\n",ans);
    return 0;
}