然后,简单翻译一下:
有n个bug,s个程序,每天能发现一个bug,求在每个程序中发现至少一个bug并将每一个bug都至少发现一次的期望天数。典型的期望dp。
如果忘了什么是期望之类的,出门左转数学选修2-3。
方案一:列分布列
很不幸,我们发现在比较差的情况下,也就是总在发现同一个bug时,我们将需要无穷天才能将bug找全。也就是说分布列将有无穷项,明显不可行。
方案二:dp[i][j]记录在j个系统中发现i个bug的期望天数
问题和方案一一样,不再重复了
方案三:dp[i][j]记录j个系统中发现i个bug后距成功的期望天数
这个方案是可行的,只要输出时输出dp[0][0]即可,在这里,dp[n][s]为0,然后自大而小转移到dp[0][0]即可。
有了状态,就需要转移方程了
能转移到dp[i][j]的共有四种情况:
1.新bug,新系统:值:(dp[i+1][j+1]+1),概率:(n-i)(s-j)/ns
2.新bug,旧系统:值:(dp[i+1][j]+1),概率:i(s-j)/ns
3.旧bug,新系统:值:(dp[i][j+1]+1),概率:(n-i)j/ns
4.旧bug,旧系统:值:(dp[i][j]+1),概率:ij/ns
也就是说:dp[i][j]=(dp[i+1][j+1]+1)(n-i)(s-j)/ns+(dp[i+1][j]+1)i(s-j)/ns+(dp[i][j+1]+1)(n-i)j/ns+(dp[i][j]+1)ij/ns,这时,我们发现等式两侧都有dp[i][j],我们需要把它整理出来
原式
现在,我们将dp[i][j]整理了出来,现在就是代码的问题了,在发标程之前,本蒟蒻说明一件事:
输出时要写成
而不是
虽然dp数组是double,但用”%.4lf”输出就会WA,此类题目精度是非常令人头疼的,本题有spj也并未卵用。
好了,上标程
Original: https://www.cnblogs.com/Grharris/p/10349841.html
Author: Grharris
Title: 题解poj2096
原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/578012/
转载文章受原作者版权保护。转载请注明原作者出处!