题意

给定一个序列,一些位置未确定(是 \(

o\)

 与 \(

x\)

 的几率各占 \(50\%\) )。对于一个 \(o/x\) 序列,连续 \(x\) 长度的 \(o\) 会得到 \(

x^2\) 

的收益,求最终得到的序列的期望收益。

分析

利用期望可加性差分, \(\delta E=E_{(x+1)^2}-E_{x^2}=2E_{x}+1\)。

于是对于 \(o\) 的位置,显然 \(E(x)=E(x-1)+1.0,f(x)=f(x-1)+\delta E\) ;

对于 \(x\) 的位置,显然 \(E(x)=0,f(x)=f(x-1)\) ;

对于 \(?\) 的位置,只需要考虑 \(o\) 的情况,因为 \(x\) 不会产生新的贡献,即 \(E(x)=(E(x-1)+1.0)*0.5,f(x)=(f(x-1)+E(x-1))*0.5\) 。

 


发表评论

电子邮件地址不会被公开。 必填项已用*标注