shyyhs

DP专题

图论(4) 多校补题(2) 数据结构(27) 数论(4) 日记(14) 未归档(38) 题解(330)

/ 注册

全部文章 / DP专题（共2篇）

1426

大概这才是期望dpdpdp的入门题吧. 可以合并当前项的dpdpdp哦！首先定义方程fif_ifi表示已经拿到了iii个,还需要拿多少次能全部拿完的期望. 那么容易得到转移方程: fi=fi∗(i/n)+fi+1∗(1−i/n)+1f_i=f_i*(i/n)+f_{i+1}*(1-i/n)+1f...

期望dp

2022-08-10

0 510

Rating 来自专栏

误入点分治题单的一个期望dp.对于这个题来说,我们不妨设置f[i]为i-1分到i分所需要的次数(我们把50分看做1分.),然后他的转移也不难.对于f[i-1]来说,它可以一步就就到f[i],也可能-2再到f[i],所以概率方程就是: f[i]=p+(1-p)*(1+f[i-2]+f[i-1]+f...

期望DP

2020-11-09

7 791