题目：http://poj.org/problem?id=2096
显然可以得到状态 $f(i,j)$ 表示集齐了i种BUG，来自于j个系统距离集齐的期望步数。
然后有
$f(i,j) -> f(i,j) \ P0 = i/n \cdot j/m$
$f(i+1,j) -> f(i,j)\ P1 = (1-i/n) \cdot j/m$
$f(i+1,j) -> f(i,j) \ P2 = i/n \cdot (1-j/m)$
$f(i+1,j+1) -> f(i,j)\ P3 = (1-i/n) \cdot (1-j/m)$
可以发现是无限的递推式形如：
$f(i,j) = i/n \cdot j/s \cdot (f(i,j) + 1) + S$
$f(i,j) = (ij) / (nm-ij) + (ns)/(ns - ij) \cdot S$
这里$S$表示的是$P1\cdot f(i+1,j)$ $P2 \cdot f(i,j+1)$ $P3 \cdot f(i+1,j+1)$等等
然后就可以做了
#include <cstdio> #include <cstring> #include <algorithm> #define N 1010 #define LD double using namespace std; int n,m; LD f[N][N]; LD S(int i,int j){ LD ans=0; if(i<n) ans += (1.0-i/(LD)n) * j/(LD)m * (1.0 + f[i+1][j]); if(j<m) ans += i/(LD)n * (1.0-j/(LD)m) * (1.0 + f[i][j+1]); if(i<n&&j<m) ans += (1.0-i/(LD)n) * (1.0-j/(LD)m) * (1.0 + f[i+1][j+1]); return ans; } int main(){ scanf("%d%d",&n,&m); f[n][m]=0; for(int i=n;~i;i--) for(int j=m;~j;j--){ if(i==n&&j==m) continue; f[i][j] = i*j/(LD)(n*m-i*j) + (n*m)/(LD)(n*m-i*j)*S(i,j); } printf("%.4lf\n",f[0][0]); return 0; }
原文：http://www.cnblogs.com/lawyer/p/4564644.html
