【期望DP】[poj2096]Collecting Bugs

妖狐艹你老母 2023-06-01 06:08 108阅读 0赞

偷一波翻译:

工程师可以花费一天去找出一个漏洞——这个漏洞可以是以前出现过的种类,也可能是未曾出现过的种类,同时,这个漏洞出现在每个系统的概率相同。要求得出找到n种漏洞,并且在每个系统中均发现漏洞的期望天数。

Translated By 大米饼

求期望天数…那就推式子吧:dp[i][j]表示已经找出了i个漏洞,已经出现在了j个系统中的期望天数

dp[i][j]=(dp[i][j]+1)*\frac{i*j}{s*n}+(dp[i][j+1]+1)*\frac{i*(s-j)}{n*s}+(dp[i+1][j]+1)*\frac{(n-i)*s}{n*s}+(dp[i+1][j+1]+1)*\frac{(n-i)*(s-j)}{n*s}

应该都能看得懂我写了什么东西吧…

然后等式左右都出现了f[i][j],那就没法转移了吗?

移项就好了qaq

然后显然要逆推初始化dp[n][s]=0,最终结果在dp[0][0]上面

  1. 1 #include<iostream>
  2. 2 #include<cstdio>
  3. 3 #define writeln(x) write(x),puts("")
  4. 4 #define writep(x) write(x),putchar(' ')
  5. 5 using namespace std;
  6. 6 inline int read(){
  7. 7 int ans=0,f=1;char chr=getchar();
  8. 8 while(!isdigit(chr)){
  9. if(chr=='-') f=-1;chr=getchar();}
  10. 9 while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
  11. 10 return ans*f;
  12. 11 }void write(int x){
  13. 12 if(x<0) putchar('-'),x=-x;
  14. 13 if(x>9) write(x/10);
  15. 14 putchar(x%10+'0');
  16. 15 }const int M = 1005;
  17. 16 double dp[M][M];
  18. 17 int n,s;
  19. 18 int main(){
  20. 19 while(~scanf("%d%d",&n,&s)){
  21. 20 dp[n][s]=0;
  22. 21 for(int i=n;i>=0;i--)
  23. 22 for(int j=s;j>=0;j--){
  24. 23 if(i==n&&j==s) continue;
  25. 24 dp[i][j]=dp[i+1][j]*(n-i)*j+dp[i][j+1]*i*(s-j)+dp[i+1][j+1]*(n-i)*(s-j)+n*s;
  26. 25 dp[i][j]/=1.0*(n*s-i*j);
  27. 26 }
  28. 27 printf("%.4lf\n",dp[0][0]);
  29. 28 }
  30. 29 return 0;
  31. 30 }

转载于:https://www.cnblogs.com/zhenglw/p/11282254.html

发表评论

表情:
评论列表 (有 0 条评论,108人围观)

还没有评论,来说两句吧...

相关阅读

    相关 期望、方差

    一、期望和方差的定义 随机变量(Random Variable) X 是一个映射,把随机试验的结果与实数建立起了一一对应的关系。而期望与方差是随机变量的两个重要的数字特征

    相关 poj2096 概率dp入门

    题意: 一个系统有s个子系统,一共会产生n中bug。某人一天可以发现一个bug,这个bug属于一个子系统,属于一个种类,每个bug属于某个子系统的概率是1/s,属于某个分类的