题意

一个游戏一共有 \(n\) 个关卡,对于第 \(i\) 关,用 \(a[i]\) 时间通过的概率为 \(p[i] \),用 \(b[i]\) 通过的时间为 \(1-p[i]\) ,每通过一关后可以选择继续下一关或者时间清 \(0\) 并从第一关开始,先要求通过所有关卡的时间和不能超过 \(R\) 才算彻底通关,问直到彻底通关位置的游戏时间的期望值为多少。

分析

因为有可以从头玩,时间清零的操作,很难直接 dp。

考虑添加一个条件,已知从头玩的期望,发现添加这个条件以后可以二分。

\(f[i][j]\) 表示到第 \(i\) 关,花费了时间 \(j\) 的期望。

因为有总时间 \(R\) 的限制,倒着推就好了。

 


发表评论

电子邮件地址不会被公开。 必填项已用*标注