自动搬运

查看原文

来自洛谷，原作者为

	donghanwen1225 一只啥都不会的蒟蒻

搬运于2025-08-24 22:59:40，当前版本为作者最后更新于2024-06-19 19:04:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

高考结束了，来复健 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$ 单峰。那么就可以通过三分逐步找到所求的最大期望。

一些可能的细节：

1. $l,r$ 与准确值偏移太大时，求出的期望过小，可能由于浮点数误差而导致出错。为了方便，我们可以枚举 $r$、三分 $l$，来规避误差的影响。

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;
}