[关闭]
@ysner 2018-08-03T00:31:07.000000Z 字数 1415 阅读 2067

[CF248E]Piglet's Birthday

期望 DP


题面

给定 个货架,初始时每个上面有 个蜜罐。
次操作,每次操作形如 ,表示从货架 上任意选择 个蜜罐试吃(吃过的也还能吃),吃完后把这 个蜜罐放到 货架上去。
每次操作完之后回答所有蜜罐都被试吃过的货架数量的期望。

解析

又一次看到期望题就boom 0
状态不难,设表示第个书架,有个没被吃过的罐的期望。(其实也是概率)。
枚举货架上原有罐没被吃过的个数个罐中没被吃过的个数
原有值乘上情况如此的方案数(分吃过的罐和没吃过的罐),再除以总方案数,即得概率。
乘上所得结果?不存在的。于是这个概率就成了期望。

注意公式

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<algorithm>
  7. #include<vector>
  8. #define re register
  9. #define il inline
  10. #define ll long long
  11. #define max(a,b) ((a)>(b)?(a):(b))
  12. #define min(a,b) ((a)<(b)?(a):(b))
  13. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  14. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  15. using namespace std;
  16. const int mod=1e9+7,N=1e5+100;
  17. int n,m,a[N],b[N],Q;
  18. double dp[N][115],ans;
  19. il ll gi()
  20. {
  21. re ll x=0,t=1;
  22. re char ch=getchar();
  23. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  24. if(ch=='-') t=-1,ch=getchar();
  25. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  26. return x*t;
  27. }
  28. il double C(re int x,re int y)
  29. {
  30. if(x<y) return 0;
  31. double res=1;
  32. fp(i,1,y) res=res*(x-i+1)/i;
  33. return res;
  34. }
  35. int main()
  36. {
  37. n=gi();fp(i,1,n) a[i]=b[i]=gi(),dp[i][a[i]]=1,ans+=dp[i][0];
  38. Q=gi();
  39. while(Q--)
  40. {
  41. re int u=gi(),v=gi(),k=gi();ans-=dp[u][0];
  42. fp(i,0,a[u])
  43. {
  44. double tmp=0,t=C(b[u],k);
  45. fp(j,0,k) //printf("%lf %lf %lf %lf\n",dp[u][i+j],C(i+j,j),C(b[u]-i-j,k-j),t)
  46. tmp+=dp[u][i+j]*C(i+j,j)*C(b[u]-i-j,k-j)/t;
  47. dp[u][i]=tmp;
  48. }
  49. b[u]-=k;b[v]+=k;ans+=dp[u][0];printf("%.10f\n",ans);
  50. }
  51. return 0;
  52. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注