然后，简单翻译一下：
有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/
转载文章受原作者版权保护。转载请注明原作者出处！