当前位置: 代码迷 >> 综合 >> poj 2096 Collecting Bugs 概率dp
  详细解决方案

poj 2096 Collecting Bugs 概率dp

热度:66   发布时间:2024-01-19 05:33:53.0

代码:

//poj 2096
//sep9
#include <iostream>
#include <cmath>
using namespace std;
double E[1005][1005];int main()
{int n,s;while(scanf("%d%d",&n,&s)==2){for(int i=0;i<=n+1;++i)for(int j=0;j<=s+1;++j)E[i][j]=0;for(int i=n;i>=0;--i)for(int j=s;j>=0;--j){if(i==n&&j==s)continue;double p0=1.0-(double(i*j))/n/s;double p1=(double (i*(s-j)) )/n/s;double p2=(double ((n-i)*j) )/n/s;double p3=(double ((n-i)*(s-j)) )/n/s;E[i][j]=p1*E[i][j+1]+p2*E[i+1][j]+p3*E[i+1][j+1]+1;E[i][j]/=p0;}	printf("%.4lf\n",E[0][0]);	}return 0;	
}