Luogu5155 [USACO18DEC]Balance Beam

题目链接:洛谷


这道题看起来是个期望题,但是其实是一道计算几何(这种题太妙了)

首先有一个很好的结论,在一个长度为$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$,这种策略

上一篇:[NLP] beam search的简单案例实现


下一篇:Apache beam中的便携式有状态大数据处理