
 /**//*
題意:目的是需要找出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
搜索
最新評論

|
|