/**//* 题意:目的是需要找出n种bug,且每个subcomponents至少出现一个bug dp[i,j]表示现在已经找出了n种bug、j个subcomponents已经有bug了离目标的期望值 那么有4种情况: 没找到新bug且没发现新的subcomponents有bug ; 发现一个新bug没发现新的subcomponents有bug 新的subcomponents有bug,但不是新种类 ;新的subcomponents发现bug,且是新种类
dp[i,j] = i*j/ns*dp[i,j] + (n-i)j/ns*dp[i+1,j] + i(s-j)/ns*dp[i,j+1] + (n-i)(s-j)/ns*dp[i+1,j+1] */ #include<cstdio>
double dp[1005][1005];
int main() { int n,s; scanf("%d%d",&n,&s); dp[n][s]=0.0; double ns=n*s; for(int i=n;i>=0;i--) for(int j=s;j>=0;j--) { if(i==n&&j==s)continue;// //化为避免用除法会快点! dp[i][j]=(ns + (n-i)*j*dp[i+1][j] + i*(s-j)*dp[i][j+1] + (n-i)*(s-j)*dp[i+1][j+1]) / (ns-i*j); } printf("%.4f\n",dp[0][0]); return 0; }
|
|
常用链接
随笔分类
Links
搜索
最新评论
|
|