首页 > 代码库 > poj2096 Collecting bugs 概率dp
poj2096 Collecting bugs 概率dp
链接:http://poj.org/problem?id=2096
大意就是讲:n种bug,s个子区域,每天随机在某个区域找一种,问期望找全的时间。
考虑每一种状态,对于每一个f[i][j](表示找了i种,j个区域),在下一天有四种转移可能:
1、在没找过的区域中找到一种没出现过的bug,即转移到f[i+1][j+1],这样做的可能性为{((n-i)/n)*((s-j)/s)},记为s1。
2、在没找过的区域中找到一种出现过的bug,即转移到f[i][j+1],可能性为{(i/n)*((s-j)/s)},记为s2。
3、在找过的区域中找到一种没出现过的bug,即转移到f[i+1][j],可能性为{((n-i)/n)*(j/s)},记为s3。
4、在找过的区域中找到一种出现过的bug,即停留在f[i][j],可能性为{(i/n)*(j/s)},记为s4。
那么转移方程就是f[i][j]=f[i+1][j+1]*s1+f[i][j+1]*s2+f[i+1][j]*s3+f[i][j]*s4+1,
化简可以得到f[i][j]=(f[i+1][j+1]*s1+f[i][j+1]*s2+f[i+1][j]*s3+1)/(1-s4),这也就是倒推期望的式子。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 using namespace std; 7 const int maxn=1005; 8 int n,s; 9 double dp[maxn][maxn],p1,p2,p3,p4; 10 int haha() 11 { 12 while(scanf("%d%d",&n,&s)!=EOF) 13 { 14 memset(dp,0,sizeof(dp)); 15 for(int i=n;i>=0;i--) 16 for(int j=s;j>=0;j--) 17 { 18 if(i==n&&j==s)continue; 19 p1=(n-i)*(s-j)*1.0; 20 p2=(n-i)*j*1.0; 21 p3=i*(s-j)*1.0; 22 p4=n*s-i*j*1.0; 23 dp[i][j]=(p1*dp[i+1][j+1]+p2*dp[i+1][j]+p3*dp[i][j+1]+n*s)/p4; 24 } 25 printf("%.4lf\n",dp[0][0]); 26 } 27 return 0; 28 } 29 int sb=haha(); 30 int main(){;}
poj2096 Collecting bugs 概率dp
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。