| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 4873 | Accepted: 2131 |
Description
Input
Output
Sample Input
2 2 2 0.9 0.9 1 0.9 0 0 0
Sample Output
0.972
分析：求保证每个队至少做对一题，冠军队做对n个题的概率。
保证每个队至少做对一题，冠军队做对n个题的概率=每个队至少做对一道题-没有一个队做到n到题。（每个队最多做了n-1个题），
dp[i][j][k]表示第i个对做到j题，目前做对了k题。
dp[i][j[k]=dp[i][j-1][k]*(1-a[i][j])+dp[i][j-1][k-1]*a[i][j];
s[i][k]表示i对至少做对了k题的概率
注意边界。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; double dp[1005][40][40]; int main() { int m,t,n,i,j,k; double a[1005][40],cnt,ans,sum,s[1005][40]; while(~scanf("%d%d%d",&m,&t,&n)) { memset(dp,0,sizeof(dp)); memset(s,0,sizeof(s)); cnt=1; ans=1; sum=1; if(m==0&&t==0&&n==0) break; for(i=1;i<=t;i++) { for(j=1;j<=m;j++) { scanf("%lf",&a[i][j]) ; cnt*=(1-a[i][j]); } ans*=(1-cnt); cnt=1; } for(i=1;i<=t;i++) { dp[i][1][0]=1-a[i][1]; dp[i][1][1]=a[i][1]; for(j=2;j<=m;j++) dp[i][j][0]=dp[i][j-1][0]*(1-a[i][j]); for(j=2;j<=m;j++) { for(k=1;k<=j;k++) { dp[i][j][k]=dp[i][j-1][k]*(1-a[i][j])+dp[i][j-1][k-1]*a[i][j]; } } for(k=1;k<=n-1;k++) s[i][n-1]+=dp[i][m][k]; } for(i=1;i<=t;i++) { sum*=s[i][n-1]; } printf("%.3lf\n",ans-sum); } return 0; }
原文：http://www.cnblogs.com/cancangood/p/3915756.html