【POJ 2096】Collecting Bugs 概率期望dp
题意
有s个系统,n种bug,小明每天找出一个bug,可能是任意一个系统的,可能是任意一种bug,即是某一系统的bug概率是1/s,是某一种bug概率是1/n。
求他找到s个系统的bug,n种bug,需要的天数的期望。
分析
计算期望E=∑所有可能需要的天数*概率
找到s个系统n种bug,需要最少max(s,n)天,而可能的天数是无穷的,这样计算很复杂,复杂到算不了。
所以考虑dp,期望E=∑(昨天可以转移到现在状态的所有可能的情况的期望+1)*概率=∑(昨天可以转移到现在状态的所有可能的情况的期望)*概率 +1
一开始我想用dp[i][j]表示已经找到i种bug,j个系统里找到bug,的期望天数,但是这样不能推出来,由【i-1,j】【i,j-1】【i,j】【i-1,j-1】四种状态推的话,需要1天的概率我们知道,但是这四种情况的概率加起来不等于1,也就是还有需要2天3天...的情况,概率很复杂计算更复杂(回到上面的复杂去了)
所以要dp[i][j]表示已经找到i种bug,j个系统里找到bug,离目标还需要的期望天数。
好,如果明天找到一个bug。
它就可以转移到这里:
dp[i+1][j] 不属于i种,属于j个系统之一。 概率为p1=(n-i)/n* j/s 。
dp[i][j+1] 属于i种之一,不属于j个系统。 概率为p2=(s-j)/s* i/n
dp[i+1][j+1] 不属于i种,不属于j个系统。 概率为p3=(n-i)/n*(s-j)/s
dp[i][j] 属于i种之一,属于j个系统之一。 概率为p4=i/n* j/s
也就是比如找到了新种类,已知系统的bug,那明天离到达目标的期望天数就是dp[i+1][j],那就是今天还差dp[i+1][j]+1天。
dp[i][j]就是它找到的没有用的bug,那明天浪费了,那今天还差dp[i][j]+1天。今天和明天的dp[i][j]是一样的。
p1+p2+p3+p4=1,所以有下面这个式子。
dp[i][j]=dp[i+1][j]*p1+dp[i][j+1]*p2+dp[i+1][j+1]*p3+dp[i][j]*p4 +1
移项然后变成这样:dp[i][j]= ( n*s + (n-i)*j*dp[i+1,j] + i*(s-j)*dp[i,j+1] + (n-i)*(s-j)*dp[i+1,j+1] )/( n*s - i*j )
我们知道dp[n][s]=0,就是已经到达目标,还需要0天。然后逆推。
代码
#include<cstdio> #define N 1005 double d[N][N]; int main() { int n,s; scanf("%d%d",&n,&s); for(int i=n; i>=0; i--) for(int j=s; j>=0; j--) { if(i!=n||j!=s) d[i][j]=(d[i+1][j]*(n-i)*j+d[i][j+1]*i*(s-j)+d[i+1][j+1]*(n-i)*(s-j)+n*s)/(n*s-i*j); } printf("%.4f",d[0][0]); return 0; }
相关文章
- poj 2385 Apple Catching dp
- ZOJ 3494 BCD Code (AC自己主动机 + 数位DP)
- 【POJ 3071】 Football(DP)
- 【BZOJ2525】[Poi2011]Dynamite 二分+树形DP
- 【BZOJ4861】[Beijing2017]魔法咒语 矩阵乘法+AC自动机+DP
- BZOJ 1087 [SCOI2005]互不侵犯King (状压DP)
- POJ 1739 Tony's Tour (DP)
- POJ 2686 Traveling by Stagecoach (状压DP)
- POJ 1185 炮兵阵地 (状压DP)
- POJ 3280 Cheapest Palindrome (区间DP)
- UVa 11584 Partitioning by Palindromes (简单DP)
- POJ 3252 Round Numbers (数位DP)
- HDU 4734 F(x) (数位DP)
- POJ 3744 Scout YYF I (概率DP+矩阵快速幂)
- LA 3942 && UVa 1401 Remember the Word (Trie + DP)
- 【POJ 1112】Team Them Up!(二分图染色+DP)
- 【POJ 2342】Anniversary party(入门树形dp)
- poj - 1953 - World Cup Noise(dp)
- POJ 1088: 滑雪(经典 DP+记忆化搜索)
- poj 2068 Nim(博弈dp)
- HDU 2845 Beans(dp)
- nyoj 61-传纸条(一)(双向dp)
- 【bzoj4872】[Shoi2017]分手是祝愿 数论+期望dp
- 1235: 入学考试[DP]