HDU6568
老套路定义 d p [ i ] dp[i] dp[i]是机器人到达 i i i位置的期望
首先 d p [ i − 1 ] + 1 dp[i-1]+1 dp[i−1]+1是固定部分,因为要先走到 i − 1 i-1 i−1,再用一步做出选择
Ⅰ . i − 1 有 ( 1 − p ) 的 概 率 走 到 i , 此 时 不 需 要 额 外 花 费 \color{Red}Ⅰ.\ i-1有(1-p)的概率走到i,此时不需要额外花费 Ⅰ. i−1有(1−p)的概率走到i,此时不需要额外花费
Ⅱ . i − 1 有 p 的 概 率 被 丢 弃 \color{Red}Ⅱ.i-1有p的概率被丢弃 Ⅱ.i−1有p的概率被丢弃
那 么 可 能 在 i − 1 那么可能在i-1 那么可能在i−1位置就找回,此时概率是 q q q
那 么 可 能 在 i 那么可能在i 那么可能在i位置就找回,此时概率是 q ( 1 − q ) q(1-q) q(1−q)
可 能 在 i + 1 可能在i+1 可能在i+1位置找回,此时概率是 q ( 1 − q ) 2 q(1-q)^2 q(1−q)2
…
也可能一直到 n n n都没找回,此时概率是 1 − 之 前 的 概 率 1-之前的概率 1−之前的概率
所 以 对 所 有 情 况 期 望 做 前 缀 和 所以对所有情况期望做前缀和 所以对所有情况期望做前缀和
#include <bits/stdc++.h> using namespace std; const int maxn=2e5+10; int l; double p,q,x[maxn],preq[maxn],dp[maxn],z[maxn],sumn[maxn]; int main() { while( cin >> l >> p >> q ) { int bit=2; double bq=q*(1-q); z[0]=1; preq[0]=q; for(int i=1;i<=l;i++) { z[i]=z[i-1]*(1-q); x[i]=bq*bit+x[i-1]; preq[i]=preq[i-1]+bq; bit+=2, bq*=(1.0-q); } dp[0]=0; double ans=0; for(int i=1;i<=l;i++) { int last = l-i; dp[i]=dp[i-1]+p*( x[last]-dp[i-1]+(1.0-preq[last])*2*(last+1) ); dp[i] = dp[i]/(1.0-p)+1; } printf("%.7lf\n",dp[l] ); } }