CodeForces 1009E Intercity Travelling 概率DP

概率DP"/>

CodeForces 1009E Intercity Travelling 概率DP

原题链接

题意

• 给我们一个长为n的序列，要求我们从头开始向右走n个节点，每个位置都有1 / 2的概率将我们传送回1号点之前，不过我们只需要完成走n步的任务就可以了。求我们走过的元素和 乘以 2的n - 1次方的期望。
  
  

思路

• 重点主要是将题意翻译为上面的“传送回一号元素之前”，这样我们就可以从1号位置考虑。
  
  

• 我们定义 F [ i ] F[i] F[i] 为“已经走了i步，走完剩下的步数，获得的元素和乘以2的n - i - 1次方的期望”，也就是原问题的一个子问题
  
  

• 然后我们可以想到初始状态

F [ n ] = 0 , F [ n − 1 ] = a 1 F[n] = 0, F[n - 1] = a_1 F[n]=0,F[n−1]=a1​

• 然后继续推可知

F [ n − 2 ] = a 1 + F [ n − 1 ] + ( a 1 + a 2 ) F [ n − 3 ] = a 1 ∗ 2 + F [ n − 2 ] + ( a 1 + a 2 ) + F [ n − 1 ] + ( a 1 + a 2 + a 3 ) F [ n − 4 ] = a 1 ∗ 4 + F [ n − 3 ] + ( a 1 + a 2 ) ∗ 2 + F [ n − 2 ] + ( a 1 + a 2 + a 3 ) + F [ n − 1 ] + ( a 1 + a 2 + a 3 + a 4 ) F[n - 2] = a_1 + F[n - 1] + (a_1 + a_2)\\ F[n - 3] = a_1 * 2 + F[n - 2] + (a_1 + a_2) + F[n - 1] + (a_1 + a_2 + a_3)\\ F[n - 4] = a_1 * 4 + F[n - 3] + (a_1 + a_2) * 2 + F[n - 2] + (a_1 + a_2 + a_3) + F[n - 1] + (a_1 + a_2 + a_3 + a_4) F[n−2]=