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)\) 。可以接受。
标签:Name,sum,猜出来,CF498B,times,Tune From: https://www.cnblogs.com/zhouzizhe/p/16911947.html