CF498B Name That Tune

 OI / CodeForces
被浏览

作为一道英文题先解释一下题意。

用 $T$ 秒时间按顺序听 $N$ 首歌,第 $i$ 首歌播放时间为 $t_i$ 秒,且每播放一秒都会有 $p_i$ 的概率被识别出来,跳到下一首。某首歌播放时间过完默认被识别,也跳到下一首。若时间有剩余而歌已全部听完则直接结束。求识别出歌数量的期望。

看见题目就想到期望DP。

第一眼想到的方程是设 $f_{i,j}$ 表示第 $i$ 秒识别到第 $j$ 首歌的期望,不难想出一个 $O(n^3)$ 的算法。

枚举一个 $k$ 表示第 $j$ 首歌已经放了几秒,注意一下边界即可。