http://poj.org/problem?id=2096
有 n 种病毒, s 个服务器, 每天等概率的在某个服务器上发现某一种病毒, 问发现所有种类病毒且覆盖所有的服务器的期望天数.
利用全期望公式可以将期望分解为子期望的加权和, 权值就是子期望发生的概率 Pi, 注意 SUM{Pi}=1;
假如我们已经完成了(i,j), 目标是(n,s), 那么下一天可能是(i,j) ,(i+1,j) ,(i,j+1) ,(i+1,j+1) 对应的 Pi 分别是 p1=(i/n)*(j/s) p2=(1-i/n)*(j/s) p3=(i/n)*(1-j/s) p4=(1-i/n)*(1-j/s)
设 f(i,j)为完成了 (i,j) 距离目标的期望, 那么有 f(i,j)=p1*(f(i,j)+1)+p2*(f(i+1,j)+1)+p3*(f(i,j+1)+1)+p4*(f(i+1,j+1)+1) | f(n,s)=0 , 移项解出 f(i,j)即可.
- #include<iostream>
- #include<cstring>
- #include<queue>
- #include<cstdio>
- #include<stack>
- #include<set>
- #include<map>
- #include<cmath>
- #include<ctime>
- #include<time.h>
- #include<algorithm>
- using namespace std;
- #define mp make_pair
- #define pb push_back
- #define debug puts("debug")
- #define LL long long
- #define pii pair<int,int>
- #define eps 1e-12
- double f[1100][1100];
- int main()
- {
- int n,m,i,j,k,t;
- cin>>n>>m;
- for(i=n;i>=0;--i){
- for(j=m;j>=0;--j){
- if(i==n&&j==m) continue;
- double p1=(double)i*j,p2=(double)j*(n-i),
- p3=(double)i*(m-j),p4=(double)(n-i)*(m-j);
- p1/=(1.0*n*m);p2/=(1.0*n*m);p3/=(1.0*n*m);p4/=(1.0*n*m);
- f[i][j]=p1+p2*(f[i+1][j]+1)+p3*(f[i][j+1]+1)+
- p4*(f[i+1][j+1]+1);
- f[i][j]/=(1.0-p1);
- }
- }
- printf("%.4f\n",f[0][0]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2583924.html