本文共 999 字，大约阅读时间需要 3 分钟。

二刷这题,做起来思路非常清晰,但是细节问题却调了几十分钟…醉了

定义$f[i]$为和机器人在点$i$剩余的期望步数

若下一步没有丢下机器人

$$(1-p)\ast (f[i+1]+1)$$

若下一步丢下了机器人,可能立马发现机器人,也可能下一步发现…

最后到了$l$,就是剩余所有可能性了

$$p\ast (q\ast (1-q{)}^{0}f[i]+q\ast (1-q{)}^{1}f[i]+q\ast (1-q{)}^{2}f[i]...)$$

发现$1-q$的次方是一个等比数列,使用前缀和来优化转移

#include 
   
    using namespace std;const int maxn = 1e5+10;double f[maxn],pre[maxn],c[maxn];int main(){
       int l,chu; double p,q,base;    while( cin >> l >> p >> q )    {
   	    base = q; chu = 0;	    for(int i=1;i<=l+2;i++)		{
   			pre[i] = pre[i-1]+base;			c[i] = c[i-1]+base*chu;			chu += 2;			base *= (1-q);		}		f[l] = 0;	    for(int i=l-1;i>=0;i--)	    {
   	    	int yu = l-i;	    	double kl = 1.0-pre[yu];	        f[i] = (f[i+1]+1)*(1-p)+p*c[yu]+p*kl*(2*l-2*i);	        if( 1.0-p!=0 )   f[i] /= ( 1.0-p );	    //	f[i] = f[i]+1;		}		printf("%.8lf\n",f[0]);	}}
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/109613045 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！