【期望DP】[poj2096]Collecting Bugs

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

偷一波翻译：

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

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

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

[Link 1]: https://www.cnblogs.com/Paul-Guderian/p/7624039.html