题目链接:洛谷
这道题看起来是个期望题,但是其实是一道计算几何(这种题太妙了)
首先有一个很好的结论,在一个长度为$L$的数轴上,每次从$x$处出发,不停地走,有$\frac{x}{L}$的概率从右端点掉下去,$\frac{L-x}{L}$从左端点掉下去。
这个证明的话,感性理解一下。
令$f_x$表示从$x$处掉到左端点的概率,则$f_0=1,f_L=0$,且对于$x\in (0,L)$,$f_x=\frac{f_{x-1}+f_{x+1}}{2}$,所以$f_x$构成一个等差数列,所以得证。
显然,我们肯定是不能一直走的,不然得分肯定是0,但是我们可以“掉进”一些权值比较高的点使得答案最优,我们称这些点为“停止点”。
设从$x$处出发,$x$左右两侧的最近的停止点为$a,b$,这种策略