CF498B Name That Tune

你有 \(T\) 秒的时间猜歌，每首歌有 \(t_i\) 秒，每一秒猜出这首歌的概率为 \(p_i\%\) ，若猜出则直接跳到下一首，若猜完所有歌则提前结束，求在 \(T\) 秒后期望在第几首歌上。 \(n,T\leq 5000\) 。

CF 的 *2400 变成洛谷的黑题？

首先是显然的 DP ，设 \(f[i][j]\) 表示在第 \(j\) 秒从第 \(i\) 首歌猜出（或者pass）到第 \(i+1\) 首的概率。

那么则有 \(f[i][j]=f[i-1][j-t_i]\times (1-p_i)^{t_i}+\sum\limits_{k=1}^{t_i}(p_i\times(1-p_i)^{k-1}\times f[i-1][j-k]\) ，即要么没有猜出来被 pass 掉（有 \((1-p_i)^{t_i}\) 的概率），要么是前 \(k-1\) 秒没有猜出来，第 \(k\) 秒猜出来。

这样的复杂度是 \(O(n\sum t_i)\) 的，不能接受，所以要考虑优化。发现后半边式子可以优化，当算出 \(f[i][j-1]\) 而要继续算 \(f[i][j]\) 时，可以将上次算出的 \(\sum(p_i\times(1-p_i)^{k-1}\) 直接 \(\times (1-p_i)\) ，并减掉后半段不需要的部分，就是原式。那么这样复杂度就变成了 \(O(nT\log t_i)\) 。可以接受。

原文地址：http://www.cnblogs.com/zhouzizhe/p/16911947.html