信息
- ID
- 272
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- (无)
- 递交数
- 16
- 已通过
- 8
- 上传者
类似地,我们设 dpi,j 表示袋子里还剩 i 个红球,j 个黑球的期望,然后我们把这个拿球的操作看成往里面放求的操作
显然地,dpi,0=i , dp0,i=0
显然地,根据题意转移有:
$$dp_{i,j}=\frac{i}{i+j} \times (dp_{i-1,j}+1) + \frac{j}{i+j} \times (dp_{i,j-1} + 1) $$答案为 dpn,m
dpi,j-1 -1